从所有组合的假设列表中获取索引排列的算法？

Question

我的意思是：

假设我们有 X 种颜色和一个由 16 个正方形组成的 4x4 网格，我们可以为任何个具有任意颜色的方块。

假设您可以生成所有可能配置的列表，并且算法将它们一个接一个地吐出（configuration#1，然后是 configuration#2 等等），有没有办法使用数字i 并立即获得 configuration#i？

（因为存储 1e+16 配置在普通硬件上是不可能的）

而且更重要的是，是否可以使用该算法的逆运算并为其提供一个配置，为此它将 return 一个 i 重新插入时将 return原来的配置？像这样：

int colours[4][4] = GenerateSomeConfig(); // Gets some combination of colours
int i = GetIndex(colours); // This is the main function I was asking about
int colours2[4][4] = GetConfig(i); // This is the reverse of GetIndex()

assert(CompareGridsEqual(colours, colours2)); // This shouldn't break

Answer 1

这些是重复的组合。

总之。让我们稍微简化一下问题。假设我们有 10 种颜色。编号为 0 到 9。让我们也为我们的方块编号，从 1 到 16（或其他。你说 4x4，你的代码说 16x16 但这并不重要）。

您可以使用方框颜色的数量。所以你最终会说：

现在你可以把网格变成条纹 - 0 9 6 3 4 7 5 1 0 2 1 7 5 2 3 4。删除空格，您就有了映射。

要使用不同数量的颜色，请使用不同的基色。不同大小的网格将导致编码数字中的数字位数不同。

你应该能够从这个提示中脱颖而出。我不会编写一个 c++ 实现来匹配你的努力 =P，我认为你应该能够做到。唯一的技术难点是处理任意基数。

Answer 2

正如我在评论中所说，每个生成配置的算法都可以创建一个包装器，将配置转换为整数，反之亦然。

最简单和通用的解决方案是这样的：

config_t GetConfig(size_t index)
{
    Generator gen;
    for(size_t i = 0; i < index; ++i) gen.GetNextConfig();
    return gen.GetNextConfig();
}


size_t GetIndex(const config_t & conf)
{
    size_t ret = 0;
    Generator gen;
    while(gen.GetNext() != conf) ++ret;
    return ret;
}

这显然不是很有效的方法，但它表明这是可能的。如果你需要更有效地做到这一点，你可能不得不牺牲通用性并专门为一个生成器实现它。 @luk32 的回答向您展示了一个非常简单的生成器的实现方式，但是当然可以有更复杂的生成器。

从所有组合的假设列表中获取索引排列的算法？

Algorithm to get permutation from an index from the hypothetical list of all combinations?

c++

algorithm

permutation

combinatorics