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

here is what I mean:

这就是我的意思:

Assuming we have X number of colours and a 4x4 grid of 16 squares, we can colour any of the squares with any colour.

假设我们有X个颜色和16个正方形的4x4网格,我们可以用任何颜色为任何正方形着色。

Assuming you can generate a list of all possible configurations and the algorithm spits them out one after another(configuration#1, then configuration#2 and so on), is there a way to use a number i and get configuration#i right off the bat?

假设您可以生成所有可能配置的列表,并且算法一个接一个地吐出(配置#1,然后是配置#2等),有没有办法使用数字i并获得配置#i蝙蝠?

(since storing 1e+16 configurations is not possible on normal hardware)

(因为在普通硬件上无法存储1e + 16配置)

And more importantly, is it possible to have an inverse of this algorithm and to instead give it a configuration, for which it will return an i that when plugged back in will return the original configuration? Something like this:

更重要的是,是否有可能得到这个算法的反转,而是给它一个配置,为此它将返回一个i,当插回时将返回原始配置?像这样的东西:

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

2 个解决方案

#1

Those are combinations with repetition.

这些是重复的组合。

Anyways. Let's simplify problem just a little bit. Let us say we have 10 colours. Numbered 0 to 9. Lets also number our squares, from 1 to 16 (or whatever. You say 4x4, your code says 16x16 but it's not important).

无论如何。让我们简单地简化一下问题。我们说我们有10种颜色。编号为0到9.让我们对正方形进行编号,从1到16(或者其他。你说4x4,你的代码说16x16,但这并不重要)。

You can use the number of the color of the box. So you would end up with lets say:

您可以使用框的颜色编号。所以你最终会说:

Now you can take the grid, and make it a stripe - 0 9 6 3 4 7 5 1 0 2 1 7 5 2 3 4. Remove spaces and you have your mapping.

现在你可以把网格,并使其成为一个条纹 - 0 9 6 3 4 7 5 1 0 2 1 7 5 2 3 4.删除空格,你有你的映射。

To use different number of colors, use different base. Different size of grid will result in different number of digits in the encoded number.

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

You should be able to take off from this hint. I'm not going to write a c++ implementation to match your effort =P, and I think you should be able to do it. The only technical difficulty is to deal with numbers of arbitrary base.

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

#2

As I said in the comment, it is possible for every algorithm that generates the configurations to create a wrapper that converts a configuration to integer and vice versa.

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

The simplest and general solution would be like this:

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

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

This is obviously not very efficient way of doing it, but it shows that it's possible. If you need to do it more efficiently you'll probably have to sacrifice generality and implement it specifically for the one generator. @luk32's answer shows you the way of doing it for a very simple generator, but of course there can be more complex generators.

这显然不是非常有效的方式,但它表明它是可能的。如果你需要更有效地做到这一点,你可能不得不牺牲一般性并专门为一个发电机实现它。 @ luk32的答案显示了为一个非常简单的生成器做这件事的方法,但当然可能有更复杂的生成器。

#1