Мне нужно вычислить перестановки итеративно. Подпись метода выглядит так:
int[][] permute(int n)
Например, для n = 3 возвращаемое значение будет:
[[0,1,2],
[0,2,1],
[1,0,2],
[1,2,0],
[2,0,1],
[2,1,0]]
Как бы вы сделали это итеративно самым эффективным способом? Я могу сделать это рекурсивно, но мне интересно видеть множество альтернативных способов сделать это итеративно.
см. алгоритм QuickPerm, он итеративный: http://www.quickperm.org/
Edit:
Переписано в Ruby для ясности:
def permute_map(n)
results = []
a, p = (0...n).to_a, [0] * n
i, j = 0, 0
i = 1
results << yield(a)
while i < n
if p[i] < i
j = i % 2 * p[i] # If i is odd, then j = p[i], else j = 0
a[j], a[i] = a[i], a[j] # Swap
results << yield(a)
p[i] += 1
i = 1
else
p[i] = 0
i += 1
end
end
return results
end
Алгоритм перехода от одной перестановки к следующей очень похож на дополнение начальной школы - когда происходит переполнение, "нести одно".
Здесь реализация, которую я написал в C:
#include <stdio.h>
//Convenience macro. Its function should be obvious.
#define swap(a,b) do { \
typeof(a) __tmp = (a); \
(a) = (b); \
(b) = __tmp; \
} while(0)
void perm_start(unsigned int n[], unsigned int count) {
unsigned int i;
for (i=0; i<count; i++)
n[i] = i;
}
//Returns 0 on wraparound
int perm_next(unsigned int n[], unsigned int count) {
unsigned int tail, i, j;
if (count <= 1)
return 0;
/* Find all terms at the end that are in reverse order.
Example: 0 3 (5 4 2 1) (i becomes 2) */
for (i=count-1; i>0 && n[i-1] >= n[i]; i--);
tail = i;
if (tail > 0) {
/* Find the last item from the tail set greater than
the last item from the head set, and swap them.
Example: 0 3* (5 4* 2 1)
Becomes: 0 4* (5 3* 2 1) */
for (j=count-1; j>tail && n[j] <= n[tail-1]; j--);
swap(n[tail-1], n[j]);
}
/* Reverse the tail set order */
for (i=tail, j=count-1; i<j; i++, j--)
swap(n[i], n[j]);
/* If the entire list was in reverse order, tail will be zero. */
return (tail != 0);
}
int main(void)
{
#define N 3
unsigned int perm[N];
perm_start(perm, N);
do {
int i;
for (i = 0; i < N; i++)
printf("%d ", perm[i]);
printf("\n");
} while (perm_next(perm, N));
return 0;
}
Использует параметр 1.9 Array # permutation?
>> a = [0,1,2].permutation(3).to_a
=> [[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]
Ниже приведена моя версия generics следующего алгоритма перестановки в С#, которая очень похожа на STL next_permutation (но она не отбрасывает коллекцию, если она уже является максимальной возможной перестановкой, как это делает версия на С++)
В теории он должен работать с любым IList < > IComparables.
static bool NextPermutation<T>(IList<T> a) where T: IComparable
{
if (a.Count < 2) return false;
var k = a.Count-2;
while (k >= 0 && a[k].CompareTo( a[k+1]) >=0) k--;
if(k<0)return false;
var l = a.Count - 1;
while (l > k && a[l].CompareTo(a[k]) <= 0) l--;
var tmp = a[k];
a[k] = a[l];
a[l] = tmp;
var i = k + 1;
var j = a.Count - 1;
while(i<j)
{
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
i++;
j--;
}
return true;
}
И демонстрационный/тестовый код:
var src = "1234".ToCharArray();
do
{
Console.WriteLine(src);
}
while (NextPermutation(src));
Здесь реализация в С# в качестве метода расширения:
public static IEnumerable<List<T>> Permute<T>(this IList<T> items)
{
var indexes = Enumerable.Range(0, items.Count).ToArray();
yield return indexes.Select(idx => items[idx]).ToList();
var weights = new int[items.Count];
var idxUpper = 1;
while (idxUpper < items.Count)
{
if (weights[idxUpper] < idxUpper)
{
var idxLower = idxUpper % 2 * weights[idxUpper];
var tmp = indexes[idxLower];
indexes[idxLower] = indexes[idxUpper];
indexes[idxUpper] = tmp;
yield return indexes.Select(idx => items[idx]).ToList();
weights[idxUpper]++;
idxUpper = 1;
}
else
{
weights[idxUpper] = 0;
idxUpper++;
}
}
}
И unit test:
[TestMethod]
public void Permute()
{
var ints = new[] { 1, 2, 3 };
var orderings = ints.Permute().ToList();
Assert.AreEqual(6, orderings.Count);
AssertUtil.SequencesAreEqual(new[] { 1, 2, 3 }, orderings[0]);
AssertUtil.SequencesAreEqual(new[] { 2, 1, 3 }, orderings[1]);
AssertUtil.SequencesAreEqual(new[] { 3, 1, 2 }, orderings[2]);
AssertUtil.SequencesAreEqual(new[] { 1, 3, 2 }, orderings[3]);
AssertUtil.SequencesAreEqual(new[] { 2, 3, 1 }, orderings[4]);
AssertUtil.SequencesAreEqual(new[] { 3, 2, 1 }, orderings[5]);
}
Метод AssertUtil.SequencesAreEqual - это специальный тестовый помощник, который можно легко воссоздать.
Я нашел версию Joey Adams наиболее читаемой, но я не смог перенести ее непосредственно на С# из-за того, как С# обрабатывает область видимости переменных for-loop. Следовательно, это слегка измененная версия его кода:
/// <summary>
/// Performs an in-place permutation of <paramref name="values"/>, and returns if there
/// are any more permutations remaining.
/// </summary>
private static bool NextPermutation(int[] values)
{
if (values.Length == 0)
throw new ArgumentException("Cannot permutate an empty collection.");
//Find all terms at the end that are in reverse order.
// Example: 0 3 (5 4 2 1) (i becomes 2)
int tail = values.Length - 1;
while(tail > 0 && values[tail - 1] >= values[tail])
tail--;
if (tail > 0)
{
//Find the last item from the tail set greater than the last item from the head
//set, and swap them.
// Example: 0 3* (5 4* 2 1)
// Becomes: 0 4* (5 3* 2 1)
int index = values.Length - 1;
while (index > tail && values[index] <= values[tail - 1])
index--;
Swap(ref values[tail - 1], ref values[index]);
}
//Reverse the tail set order.
int limit = (values.Length - tail) / 2;
for (int index = 0; index < limit; index++)
Swap(ref values[tail + index], ref values[values.Length - 1 - index]);
//If the entire list was in reverse order, tail will be zero.
return (tail != 0);
}
private static void Swap<T>(ref T left, ref T right)
{
T temp = left;
left = right;
right = temp;
}
Я также столкнулся с алгоритмом QuickPerm, указанным в другом ответе. Я тоже хотел поделиться этим ответом, потому что видел некоторые немедленные изменения, которые можно сделать, чтобы записать их короче. Например, если индексный массив "p" инициализируется несколько иначе, он сохраняет необходимость возвращать первую перестановку перед циклом. Кроме того, все те, в то время как петли и если заняли гораздо больше места.
void permute(char* s, size_t l) {
int* p = new int[l];
for (int i = 0; i < l; i++) p[i] = i;
for (size_t i = 0; i < l; printf("%s\n", s)) {
std::swap(s[i], s[i % 2 * --p[i]]);
for (i = 1; p[i] == 0; i++) p[i] = i;
}
}
Как насчет рекурсивного алгоритма, который вы можете назвать итеративно? Если вам действительно понадобится этот материал в качестве такого списка (вы должны четко указать, что вместо того, чтобы выделять кучу бессмысленной памяти). Вы можете просто вычислить перестановку "на лету" по ее индексу.
Подобно перестановке добавляется повторное обращение хвоста (а не возврат к 0), индексирование определенного значения перестановки - это поиск цифр числа в базе n, затем n-1, затем n-2... через каждую итерацию.
public static <T> boolean permutation(List<T> values, int index) {
return permutation(values, values.size() - 1, index);
}
private static <T> boolean permutation(List<T> values, int n, int index) {
if ((index == 0) || (n == 0)) return (index == 0);
Collections.swap(values, n, n-(index % n));
return permutation(values,n-1,index/n);
}
Логическое значение возвращает значение вашего индекса вне пределов. А именно, что у него закончились n значений, но осталось оставшийся индекс.
И он не может получить все перестановки для более чем 12 объектов. 12! < Integer.MAX_VALUE < 13
- Но это так очень красиво. И если вы делаете что-то неправильно, может быть полезно.
Я реализовал алгоритм в Javascript.
var all = ["a", "b", "c"];
console.log(permute(all));
function permute(a){
var i=1,j, temp = "";
var p = [];
var n = a.length;
var output = [];
output.push(a.slice());
for(var b=0; b <= n; b++){
p[b] = b;
}
while (i < n){
p[i]--;
if(i%2 == 1){
j = p[i];
}
else{
j = 0;
}
temp = a[j];
a[j] = a[i];
a[i] = temp;
i=1;
while (p[i] === 0){
p[i] = i;
i++;
}
output.push(a.slice());
}
return output;
}
Я использовал алгоритмы здесь. На странице содержится много полезной информации.
Изменить: Извините, они были рекурсивными. uray отправил ссылку на итеративный алгоритм в своем ответе.
Я создал пример PHP. Если вам действительно не нужно возвращать все результаты, я бы создал только итеративный класс следующим образом:
<?php
class Permutator implements Iterator
{
private $a, $n, $p, $i, $j, $k;
private $stop;
public function __construct(array $a)
{
$this->a = array_values($a);
$this->n = count($this->a);
}
public function current()
{
return $this->a;
}
public function next()
{
++$this->k;
while ($this->i < $this->n)
{
if ($this->p[$this->i] < $this->i)
{
$this->j = ($this->i % 2) * $this->p[$this->i];
$tmp = $this->a[$this->j];
$this->a[$this->j] = $this->a[$this->i];
$this->a[$this->i] = $tmp;
$this->p[$this->i]++;
$this->i = 1;
return;
}
$this->p[$this->i++] = 0;
}
$this->stop = true;
}
public function key()
{
return $this->k;
}
public function valid()
{
return !$this->stop;
}
public function rewind()
{
if ($this->n) $this->p = array_fill(0, $this->n, 0);
$this->stop = $this->n == 0;
$this->i = 1;
$this->j = 0;
$this->k = 0;
}
}
foreach (new Permutator(array(1,2,3,4,5)) as $permutation)
{
var_dump($permutation);
}
?>
Обратите внимание, что он обрабатывает каждый массив PHP как индексированный массив.
Я бы проголосовал или добавил комментарий, но, видимо, репутация страдает. Мне нравится это из предыдущего комментария, с несколькими настройками для прямого и обратного результатов, получения полного npr подмножества возможных перестановок и т.д. Также отображается в CSharp. Ури верна, версия готовится.