algorithm - 返回特定圆中k个元素的组合的算法

Question

它打算用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，只有左边的一个是根据规则绘制的。与右边的一样，不是“黑白黑”模式重复出现，而是相邻的扇区在大多数皇冠上不同（上面的扇区与其相邻的扇区不同）更内部。
enter image description here
我尝试过一些算法，例如使用简单的组合，但它不起作用，因为它是一个圆，所以最后一个颜色集必须与第一个颜色集匹配。

Answer 1

据我所知，这个问题需要一个算法来生成长度为n的循环k元灰码（我假设目的是m总是恰好为kn，以便所有可能的颜色序列都出现在圆中）。有关如何查找较短灰色序列的说明，请参见下文。）
灰码是一种编码系统，其中连续的码具有汉明距离1，也就是说，它们只在一个位置上不同。虽然最常见的灰色代码是二进制的，但是这个概念和算法可以很容易地扩展到任何k的基k。
经典的二进制灰码是由一个二进制数通过从“左到右”（即高阶数字优先）的累积异或数字形成的下面的算法，在不修改Wikipedia的情况下复制，将xor替换为“sum modulok”；如果k是2，也可以这样做，因为xor正是其参数的模2和。[注1和2]
我添加了一个驱动程序，它打印出k种颜色的任意n个长度序列的kn个不同序列，重复第一行，以便清楚地表明它是循环的。
实际上，很容易证明最后一个序列只在一个位置与第一个序列不同，因为将该算法应用于kn-1的结果（kn-1是完全由数字k-1组成的基数k数）在第一个位置以外的每个位置都有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 2，因为对于k=2，并非m的所有值都有解。（特别是，如果k是2，m是奇数，就没有解决方案；这可以用一个简单的奇偶性参数来证明。）
首先，假设m≥2kn-1。
如果灰色序列中的一个元素与它的前一个和它的成功者都不同，那么我将其称为final。可以看出，最终元素以长度k-2的行出现，由成对的非最终元素分隔。可以删除最后一个元素，因为它的前一个元素和它的后继元素也必须仅在其最终位置上彼此不同。有2kn-1个非最终元素，如果m≥2kn-1，我们可以删除kn-m个最终元素，并且仍然具有灰色序列。此子序列可以通过以下过滤器生成：
非最终要素
第一个M-2KN-1最终元件
第二种情况是m的值是偶数且小于k'×kn-1，其中k'是不大于k的最大偶数（即，k为偶数时k'为k，k为奇数时k-1）。在这种情况下，我们可以使用反射的灰色代码的子序列具体地说，我们使用一个灰色序列来表示混合基数，其数字权值对于高阶数字位置为k'，对于所有其他数字为k'。我们从序列开始：
Gn，由上述算法生成的序列
_n，由上述算法生成的序列的逆
现在，我们定义序列S如下：
S=0GN–-1 1 N–-1…K'284;N–-1（其中xG表示G，每个元素前面都有 x）。
应该清楚的是，s开头的第i个元素和s结尾的第i个元素只在第一个数字上有所不同。因此，我们可以使用s来产生长度为2i的灰色序列，对于任何i到k'/2。
最后，如果我们需要长度m的序列，其中m是奇数且小于k'×kn-1，我们可以使用上面的构造，省去序列中的第二个元素。
笔记
该代码将高阶数字放在数组的最后一个位置，因此“数字”实际上是先打印低阶数字。这并没有改变任何重要的事情，尽管回想起来，我最好还是把序列打印回去。
维基百科的编辑历史表明，引用的代码存在争议。如果它再次消失，我会在代码的注释中添加一个带时间戳（即永久）的url。