如何从可变数量的可变长度数组中找到由 1 个元素组成的所有排列？

Question

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

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

编辑：组数也有所不同。

Answer 1

如果您使用 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);

Answer 2

为了继续理解 Anon 所说的内容，你不能只是循环播放它们。您在类中维护状态，以便知道每个数组的最后一个索引是什么。逻辑是相同的，但是您不会在连续循环中运行。伪代码逻辑将是：

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

Answer 3

那么...这个不简单吗？

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

使用 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 的列表，并让自己确信它确实有效。

Answer 4

您可以只为每个数组中您的个人位置保留一个计数器。在 get_next 方法中，将计数器增加 1 并按数组长度对其进行 mod 。然后，每当前一个计数器变为 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 变量。