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

一尘不染

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

algorithm

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

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

编辑： 套数也有所不同。

阅读 165

2020-07-28

共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);

2020-07-28