代码之家 › 专栏 › 技术社区 › James

如何从可变长度的数组中找到由1个元素组成的所有置换?

permutation algorithm

James · 技术社区 · 14 年前

我有一个数组 U 数组的 D 长度不同。我需要能够返回数组索引的所有排列,这些排列将从每个集合中选择一个由1个元素组成的不同排列。我还要求将这个alorithm表示为一个只记住最后一个置换的对象,并使用get_next方法返回下一个置换。

例如, U = [array_of_size_n1, array_of_size_n2, array_of_size_n3] 会有 n1*n2*n3 排列,每个三元素长。

编辑: 套数也不尽相同。

4 回复 | 直到 14 年前

user97370 14 年前

如果您使用的是python,这是标准库的一部分: itertools.product . 但假设你不是,这是一个伪代码版本。

// Create an initialised array of indexes.
int[] index0(arrays) {
    // We require all arrays to be non-empty.
    for a in arrays {
        assert len(a) != 0;
    }
    return new int[len(arrays)];
}

// Increment the indices. Returns false when the indices wrap round to the start.
bool next_index(indices, arrays) {
    for (i = len(indices) - 1; i >= 0; --i) {
        indices[i] += 1
        if indices[i] < len(arrays[i]) {
            return true;
        }
        indices[i] = 0;
    }
    return false;
}

您可以这样使用它(假设您的数组都不是空的)。这个例子打印出数组中元素的每个组合。

indices = index0(arrays); 
{
    for (i = 0; i < len(arrays); ++i) {
        print arrays[i][indices[i]];
    }
    print
} while next_index(indices);

WLPhoenix 14 年前

你可以在每个数组中为你的个人位置保留一个计数器。在get_next方法中,增加一个的计数器并按数组的长度对其进行修改。然后每次前一个计数器翻到0时,就增加下一个计数器;

if (pos3 == array_of_size_n3 -1)
{
   if (pos2 == size_of_array_2 -1)
   {
       pos1 = (pos1 + 1) % size_of_array_1

   }
   pos2 = (pos2 + 1) % size_of_array_2
}
pos3 = (pos3 + 1) % size_of_array_3

print array1[pos1], array2[pos2], array3[pos3]

编辑:如果数组的数目不同,请在数组中保留位置变量。事实上,这样可能会更好。这样,就可以像引用数组本身一样引用pos变量。

San Jacinto 14 年前

要抓住阿农说的话,你不只是在他们身上兜圈子。在类中维护状态,以便知道每个数组的最后一个索引是什么。逻辑是一样的,但你不能在一个连续的循环中运行。伪代码逻辑是:

get_next()
{
  oldn3 = this.n3;
  oldn2 = this.n2;
  oldn1 = this.n1;

  if(this.n3 == this.a3.Count)
     this.n3 = 0;
  else
     this.n3++;

  if(oldn3 > this.n3)
    if(this.n2 == this.a2.Count)
      this.n2 = 0;
    else
      this.n2++;

  if(oldn2 > this.n2)
    if(this.n1 == this.a1.Count)
      this.n1 = 0;
    else
      this.n1++;

  if(oldn1 > this.n1)
    return NO_MORE_PERMS;

  return [n1,n2,n3];  
}

getCurrent()
{
  return [n1,n2,n3];
}

Anon. 14 年前

所以…这个怎么样不是直截了当?

你需要一个迭代器。您希望它在最后一个数组上迭代。当它到达该数组的末尾时,增加它在第二个最后一个数组中的当前位置,并返回到最后一个数组的开头。

使用c s的伪代码 yield return 语法:

foreach n1 in a1
    foreach n2 in a2
        foreach n3 in a3
            yield return (n1, n2, n3)

编辑:如果集合的数目不同,可以使用某种形式的递归:

function next(list)
    firstArray = list.first
    iterator = iterator(list.rest)
    if !iterator
        foreach i in firstArray
            yield return i
    else
        foreach i in firstArray
            while (iterator.hasNext)
                yield return (i, iterator.next)

考虑一下当一个长度为1的列表被传入时的行为,然后考虑一下长度为2的列表的行为,并让自己确信它确实有效。