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

Question

我有一个长度不同U的数组。D我需要能够返回数组索引的所有排列，这些排列将选择由每个集合中的 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

您可以在每个数组中为您的个人位置保留一个计数器。在您的 get_next 方法中，将计数器增加 1 并将其修改为数组的长度。然后，每次前一个计数器翻转到 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 变量。

Answer 3

那么......这不是直截了当的吗？

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

使用 C#syield 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

要了解 Anon 所说的内容，您不仅要遍历它们。您在类中维护状态，以便您知道每个数组的最后一个索引是什么。逻辑是一样的，但你不会在一个连续的循环中运行。伪代码逻辑将是：

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

  如果（this.n3 == this.a3.Count）
     这.n3 = 0;
  别的
     这个.n3++;

  if(oldn3 > this.n3)
    如果（this.n2 == this.a2.Count）
      这.n2 = 0;
    别的
      这个.n2++;

  if(oldn2 > this.n2)
    如果（this.n1 == this.a1.Count）
      这.n1 = 0;
    别的
      这个.n1++;

  if(oldn1 > this.n1)
    返回 NO_MORE_PERMS；

  返回[n1，n2，n3]；  
}

获取当前（）
{
  返回[n1，n2，n3]；
}