return 特定圆中 k 个元素的组合的算法
Algorithm to return combinantions of k elements in a specific circle
它打算用k种不同的颜色（颜色名称可以通过数字切换）绘制一个有n个圆冠和m个扇区的圆盘。为了使圆盘的绘画有一定的差异性，但又要模糊差异，绘画必须遵守以下规则：
1-每个皇冠的每个扇区只有一种颜色
2- 不能有两个完全相同颜色设置的扇区
2-两个相邻扇区的颜色可能仅与其其中一个皇冠不同
从 n=2, m=9 e K=3 的圆盘我们可以得到这个列表
[
[ "red"; "red" ],
[ "red"; "green" ],
[ "red"; "blue" ],
[ "green"; "blue" ],
[ "blue"; "blue" ],
[ "blue"; "green" ],
[ "green"; "green" ],
[ "green"; "red" ],
[ "blue"; "red" ] ]
如您所见，在建议的条件下最后一个扇区与第一个扇区相结合...
从下面的盘子来看，n=3，m=8，k=2，只有左边的盘子是按规则画的。与右边的一样，它不是重复的 "black-white-black" 模式，因为在大部分皇冠中不同的相邻扇区（上面的扇区与其相邻的邻居不同）更内部。
enter image description here
我已经尝试了一些算法，例如使用简单的组合，但它不起作用，因为它是一个圆，所以最后一个颜色集必须与第一个匹配。
据我了解，这道题要求算法生成一个循环的k-ary Gray code，长度为n . （我假设意图是 m 总是正好 kn 以便所有可能的颜色序列都出现在圆圈中。请参阅下面有关如何处理查找较短灰色序列的说明。）
格雷码是连续代码汉明距离为1的编码系统；也就是说，它们只有一个位置不同。虽然最常见的格雷码是二进制的，但对于任何 k.
，这个概念和算法可以很容易地扩展到基数 k
经典的二进制格雷码是通过对 "left to right" 中的数字进行累积异或运算（即高位在前）从二进制数形成的。以下算法从 Wikipedia 中未经修改复制，将 XOR 替换为 "sum modulo k"；如果 k 为 2，这也有效，因为 XOR 恰好是其参数的模 2 和。 [注释 1 和 2]
我添加了一个驱动程序，它打印出 kn 不同的序列n-k 颜色的长度序列，重复第一行以明确它是循环的。
实际上，很容易证明最后一个序列与第一个序列只有一个位置不同，因为将算法应用于k的结果n−1，即完全由数字k[=157组成的基数-k =]−1，除了第一个位置之外的每个位置都有一个0。
// The following was copied without modification from
// https://en.wikipedia.org/w/index.php?title=Gray_code&oldid=869851753#n-ary_Gray_code
// inputs: base, digits, value
// output: Gray
// Convert a value to a Gray code with the given base and digits.
// Iterating through a sequence of values would result in a sequence
// of Gray codes in which only one digit changes at a time.
void toGray(unsigned base, unsigned digits, unsigned value, unsigned gray[digits])
{
unsigned baseN[digits]; // Stores the ordinary base-N number, one digit per entry
unsigned i; // The loop variable
// Put the normal baseN number into the baseN array. For base 10, 109
// would be stored as [9,0,1]
for (i = 0; i < digits; i++) {
baseN[i] = value % base;
value = value / base;
}
// Convert the normal baseN number into the Gray code equivalent. Note that
// the loop starts at the most significant digit and goes down.
unsigned shift = 0;
while (i--) {
// The Gray digit gets shifted down by the sum of the higher
// digits.
gray[i] = (baseN[i] + shift) % base;
shift = shift + base - gray[i]; // Subtract from base so shift is positive
}
}
/* Here is a simple driver program to demonstrate the sequence */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(int argc, char* argv[]) {
if (argc < 3) {
fprintf(stderr, "Usage: %s N colour...\n", argv[0]);
argv = (char*[]){"3", "red", "green", "blue"};
}
unsigned n = atoi(argv[1]);
unsigned k = argc - 2;
argv += 2;
int maxlen = 1;
for (unsigned i = 0; i < k; ++i) if (strlen(argv[i]) > maxlen) maxlen = strlen(argv[i]);
maxlen += 1;
unsigned gray[n];
unsigned count = 1; for (unsigned i = n; i; --i) count *= k;
for (unsigned v = 0; v <= count; ++v) {
toGray(k, n, v, gray);
for (unsigned i = 0; i < n; ++i) printf("%-*s", maxlen, argv[gray[i]]);
putchar('\n');
}
return 0;
}
以下是此代码的一些示例运行：
./graynk 3 cyan yellow magenta ./graynk 2 red green blue ./graynk 3 black white
cyan cyan cyan red red black black black
yellow cyan cyan green red white black black
magenta cyan cyan blue red white white black
magenta yellow cyan blue green black white black
cyan yellow cyan red green black white white
yellow yellow cyan green green white white white
yellow magenta cyan green blue white black white
magenta magenta cyan blue blue black black white
cyan magenta cyan red blue black black black
cyan magenta yellow red red
yellow magenta yellow
magenta magenta yellow
magenta cyan yellow
cyan cyan yellow
yellow cyan yellow
yellow yellow yellow
magenta yellow yellow
cyan yellow yellow
cyan yellow magenta
yellow yellow magenta
magenta yellow magenta
magenta magenta magenta
cyan magenta magenta
yellow magenta magenta
yellow cyan magenta
magenta cyan magenta
cyan cyan magenta
cyan cyan cyan
现在，简单考虑一下需要生成长度为m < k[=121的不完整格雷序列的情况=]n。我在这里假设 k>2 因为对于 k=2，并不是 m 的所有值有解决办法。 （特别地，如果 k 是 2 而 m 是奇数，则没有解决方案；这可以用一个简单的奇偶校验参数来证明。）
首先，假设m ≥ 2kn−1 .
如果格雷序列中的元素仅在最终位置与其前身和后继不同，我将其称为 final。可以看出 final 元素出现在长度为 k−2 的游程中，由成对的非最终元素分隔。可以删除最终元素，因为它的前身和后继元素也必须仅在它们的最终位置上彼此不同。有2kn−1个非最终元素，如果m ≥ 2kn−1 我们可以去掉k n−m最后一个元素，仍然有一个格雷序列。该子序列可以通过以下过滤器生成：
- 非最终元素
- 第一个m−2kn−1 最终元素
第二种情况是m的值是偶数且小于k'×kn−1，其中k'是不大于[=47的最大偶数=]k。 （也就是说，如果 k 是偶数，k' 就是 k，而 k −1 如果 k 是奇数。）在这种情况下，我们可以使用反射格雷码的子序列。具体来说，我们对混合基数使用格雷序列，其数字权重为 k' 用于高位数字位置和 k 所有其他数字。我们从序列开始：
- Gn,上述算法生成的序列
- Ĝn,将上述算法生成的序列反转
现在，我们定义序列S如下：
- S = ⟨0Gn−1⟩ ⟨1Ĝn−1⟩ … ⟨k'Ĝn−1 ⟩ （其中 ⟨xG⟩ 表示 G 每个元素前加上
x。
应该清楚，从S开始的第i个元素和i[= S 末尾的第 157=] 个元素仅在第一个数字上有所不同。因此，我们可以使用 S 为任何 i 生成长度为 2i 的格雷序列k'/2.
最后，如果我们需要长度为m的序列，其中m为奇数且小于k'×kn−1，我们可以使用上面的构造，省略序列中的第二个元素。
备注
代码将高位数字放在数组的最后一个位置，因此 "number" 实际上是先打印低位数字。这并没有改变任何重要的事情，尽管回想起来我最好还是向后打印序列。
维基百科编辑历史显示引用的代码存在争议。以防它再次消失，我在代码的注释中添加了时间戳（即永久）URL。
它打算用k种不同的颜色（颜色名称可以通过数字切换）绘制一个有n个圆冠和m个扇区的圆盘。为了使圆盘的绘画有一定的差异性，但又要模糊差异，绘画必须遵守以下规则：
1-每个皇冠的每个扇区只有一种颜色
2- 不能有两个完全相同颜色设置的扇区
2-两个相邻扇区的颜色可能仅与其其中一个皇冠不同
从 n=2, m=9 e K=3 的圆盘我们可以得到这个列表
[
[ "red"; "red" ],
[ "red"; "green" ],
[ "red"; "blue" ],
[ "green"; "blue" ],
[ "blue"; "blue" ],
[ "blue"; "green" ],
[ "green"; "green" ],
[ "green"; "red" ],
[ "blue"; "red" ] ]
如您所见，在建议的条件下最后一个扇区与第一个扇区相结合...
从下面的盘子来看，n=3，m=8，k=2，只有左边的盘子是按规则画的。与右边的一样，它不是重复的 "black-white-black" 模式，因为在大部分皇冠中不同的相邻扇区（上面的扇区与其相邻的邻居不同）更内部。
enter image description here
我已经尝试了一些算法，例如使用简单的组合，但它不起作用，因为它是一个圆，所以最后一个颜色集必须与第一个匹配。
据我了解，这道题要求算法生成一个循环的k-ary Gray code，长度为n . （我假设意图是 m 总是正好 kn 以便所有可能的颜色序列都出现在圆圈中。请参阅下面有关如何处理查找较短灰色序列的说明。）
格雷码是连续代码汉明距离为1的编码系统；也就是说，它们只有一个位置不同。虽然最常见的格雷码是二进制的，但对于任何 k.
，这个概念和算法可以很容易地扩展到基数 k 经典的二进制格雷码是通过对 "left to right" 中的数字进行累积异或运算（即高位在前）从二进制数形成的。以下算法从 Wikipedia 中未经修改复制，将 XOR 替换为 "sum modulo k"；如果 k 为 2，这也有效，因为 XOR 恰好是其参数的模 2 和。 [注释 1 和 2]
我添加了一个驱动程序，它打印出 kn 不同的序列n-k 颜色的长度序列，重复第一行以明确它是循环的。
实际上，很容易证明最后一个序列与第一个序列只有一个位置不同，因为将算法应用于k的结果n−1，即完全由数字k[=157组成的基数-k =]−1，除了第一个位置之外的每个位置都有一个0。
// The following was copied without modification from
// https://en.wikipedia.org/w/index.php?title=Gray_code&oldid=869851753#n-ary_Gray_code
// inputs: base, digits, value
// output: Gray
// Convert a value to a Gray code with the given base and digits.
// Iterating through a sequence of values would result in a sequence
// of Gray codes in which only one digit changes at a time.
void toGray(unsigned base, unsigned digits, unsigned value, unsigned gray[digits])
{
unsigned baseN[digits]; // Stores the ordinary base-N number, one digit per entry
unsigned i; // The loop variable
// Put the normal baseN number into the baseN array. For base 10, 109
// would be stored as [9,0,1]
for (i = 0; i < digits; i++) {
baseN[i] = value % base;
value = value / base;
}
// Convert the normal baseN number into the Gray code equivalent. Note that
// the loop starts at the most significant digit and goes down.
unsigned shift = 0;
while (i--) {
// The Gray digit gets shifted down by the sum of the higher
// digits.
gray[i] = (baseN[i] + shift) % base;
shift = shift + base - gray[i]; // Subtract from base so shift is positive
}
}
/* Here is a simple driver program to demonstrate the sequence */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(int argc, char* argv[]) {
if (argc < 3) {
fprintf(stderr, "Usage: %s N colour...\n", argv[0]);
argv = (char*[]){"3", "red", "green", "blue"};
}
unsigned n = atoi(argv[1]);
unsigned k = argc - 2;
argv += 2;
int maxlen = 1;
for (unsigned i = 0; i < k; ++i) if (strlen(argv[i]) > maxlen) maxlen = strlen(argv[i]);
maxlen += 1;
unsigned gray[n];
unsigned count = 1; for (unsigned i = n; i; --i) count *= k;
for (unsigned v = 0; v <= count; ++v) {
toGray(k, n, v, gray);
for (unsigned i = 0; i < n; ++i) printf("%-*s", maxlen, argv[gray[i]]);
putchar('\n');
}
return 0;
}
以下是此代码的一些示例运行：
./graynk 3 cyan yellow magenta ./graynk 2 red green blue ./graynk 3 black white
cyan cyan cyan red red black black black
yellow cyan cyan green red white black black
magenta cyan cyan blue red white white black
magenta yellow cyan blue green black white black
cyan yellow cyan red green black white white
yellow yellow cyan green green white white white
yellow magenta cyan green blue white black white
magenta magenta cyan blue blue black black white
cyan magenta cyan red blue black black black
cyan magenta yellow red red
yellow magenta yellow
magenta magenta yellow
magenta cyan yellow
cyan cyan yellow
yellow cyan yellow
yellow yellow yellow
magenta yellow yellow
cyan yellow yellow
cyan yellow magenta
yellow yellow magenta
magenta yellow magenta
magenta magenta magenta
cyan magenta magenta
yellow magenta magenta
yellow cyan magenta
magenta cyan magenta
cyan cyan magenta
cyan cyan cyan
现在，简单考虑一下需要生成长度为m < k[=121的不完整格雷序列的情况=]n。我在这里假设 k>2 因为对于 k=2，并不是 m 的所有值有解决办法。 （特别地，如果 k 是 2 而 m 是奇数，则没有解决方案；这可以用一个简单的奇偶校验参数来证明。）
首先，假设m ≥ 2kn−1 .
如果格雷序列中的元素仅在最终位置与其前身和后继不同，我将其称为 final。可以看出 final 元素出现在长度为 k−2 的游程中，由成对的非最终元素分隔。可以删除最终元素，因为它的前身和后继元素也必须仅在它们的最终位置上彼此不同。有2kn−1个非最终元素，如果m ≥ 2kn−1 我们可以去掉k n−m最后一个元素，仍然有一个格雷序列。该子序列可以通过以下过滤器生成：
- 非最终元素
- 第一个m−2kn−1 最终元素
第二种情况是m的值是偶数且小于k'×kn−1，其中k'是不大于[=47的最大偶数=]k。 （也就是说，如果 k 是偶数，k' 就是 k，而 k −1 如果 k 是奇数。）在这种情况下，我们可以使用反射格雷码的子序列。具体来说，我们对混合基数使用格雷序列，其数字权重为 k' 用于高位数字位置和 k 所有其他数字。我们从序列开始：
- Gn,上述算法生成的序列
- Ĝn,将上述算法生成的序列反转
现在，我们定义序列S如下：
- S = ⟨0Gn−1⟩ ⟨1Ĝn−1⟩ … ⟨k'Ĝn−1 ⟩ （其中 ⟨xG⟩ 表示 G 每个元素前加上
x。
应该清楚，从S开始的第i个元素和i[= S 末尾的第 157=] 个元素仅在第一个数字上有所不同。因此，我们可以使用 S 为任何 i 生成长度为 2i 的格雷序列k'/2.
最后，如果我们需要长度为m的序列，其中m为奇数且小于k'×kn−1，我们可以使用上面的构造，省略序列中的第二个元素。
备注
代码将高位数字放在数组的最后一个位置，因此 "number" 实际上是先打印低位数字。这并没有改变任何重要的事情，尽管回想起来我最好还是向后打印序列。
维基百科编辑历史显示引用的代码存在争议。以防它再次消失，我在代码的注释中添加了时间戳（即永久）URL。