logo标签列表

如何迭代计算0到N的所有可能排列？

language-agnosticmathpermutation
30

我需要迭代地计算排列。 方法签名如下：

int[][] permute(int n)

例如，对于n = 3，返回值将是：

[[0,1,2],
 [0,2,1],
 [1,0,2],
 [1,2,0],
 [2,0,1],
 [2,1,0]]

你会如何以最高效的方式迭代完成这个任务？我可以递归地完成它，但我想看到使用迭代方法的其他许多方式。

2
正如我在我的答案中所提到的（在uray建议使用QuickPerm算法后进行了编辑），最有效的方法是实时迭代排列。构建完整列表可能并不是非常有用，因为您可以仅处理当前的迭代。 - Matthew
没错，这就是为什么我在uray的答案中添加的Ruby代码使用了yield和blocks。它会在计算下一个排列之前将每个排列传递给提供的代码块。 - Bob Aman
1
请查看此问题和答案：https://dev59.com/ynRC5IYBdhLWcg3wRO3k - ShreevatsaR
@Bob，我发布的C#版本使用了相同的方法，即在结果可用时产生结果。希望能对某些人有所帮助。 - Drew Noakes
10个回答
23

请查看 QuickPerm 算法，它是迭代的：http://www.quickperm.org/

编辑：

为了更加清晰易懂，已经用 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
我悄悄地加入了一个Ruby实现这个算法，以便于我的个人参考。本来想把它放在评论里的，但那里无法进行语法高亮。 - Bob Aman
1
顺便提一下，当前版本的Ruby已经内置了这个功能：(0...n).to_a.permutation { |a| puts a.inspect } - Bob Aman
4
这个的时间复杂度是多少？ - aidan
6

从一个排列到下一个的步骤算法与小学加法非常相似 - 当发生溢出时，“进位一”。

这是我用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's 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;
}
5

使用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]]
不，我要的是算法本身。我标记为语言无关，也正是因为这个原因。 - Bob Aman
4
以下是我用泛型编写的C#下一个排列算法, 与STL的next_permutation函数相似(但如果集合已经达到最大可能的排列，它不会像C++版本那样将其反转)。理论上，它应该适用于任何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));
2

我还遇到了另一个答案中提到的QuickPerm算法。我想额外分享一下这个答案，因为我发现可以做出一些立即的改变来缩短它的代码。例如，如果索引数组“p”的初始化稍微不同，就可以在循环之前省略返回第一个排列。此外，所有那些while循环和if语句占用了更多的空间。

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;
    }
}
不错。我必须将最后一个 for 循环中的停止条件更改为 i < l && p[i] == 0。 - Xavier Dury
2

我发现Joey Adams的版本最易读，但是由于C#处理for循环变量的作用域方式不同，我不能直接将其移植到C#中。因此，这是他代码的稍微调整版本：

/// <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's 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;
}
2

这里提供一个C#的实现，作为扩展方法：

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++;
        }
    }
}

还有一个单元测试：

[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 方法是一个自定义的测试辅助工具，可以很容易地重新创建。

1
如果您需要像这样的列表（您应该明确地将其内联，而不是分配一堆无意义的内存），那么如何使用可以迭代调用的递归算法呢？您可以通过其索引即时计算排列。就像排列是将尾部重新反转（而不是恢复为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！
-- 但是，这非常漂亮。如果您做了很多错误的事情，也许会有用。
20！< Long.MAX_VALUE < 21！ - Tatarize
如果事情变得更加复杂，可能需要使用一个大数类。 - Tatarize
1
我已经在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;
}
0

我已经使用了这里的算法。该页面包含了很多有用的信息。

编辑：抱歉，之前提到的是递归算法。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数组视为索引数组。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接