It is intended to paint a disc with n circular crowns and m sectors, using k distinct colors (color names can be switched by numbers). In order for there to be some diversity in the painting of the discs, but for differences to be blurred, the painting must obey the following rules:
1- each sector in each crown has only one of the colors
2- there can not be two sectors exactly with the same color setting
2-two adjacent sectors may only differ in color from one of their crowns
From a disc with n=2, m=9 e K=3 we can get this list
[
[ "red"; "red" ],
[ "red"; "green" ],
[ "red"; "blue" ],
[ "green"; "blue" ],
[ "blue"; "blue" ],
[ "blue"; "green" ],
[ "green"; "green" ],
[ "green"; "red" ],
[ "blue"; "red" ] ]
As u can see the last sector combines with the first within the proposed conditions...
From the disks below, both with n = 3, m = 8 and k = 2, only the one on the left is painted according to the rules. Like the one on the right, it is not the "black-white-black" pattern that repeats as were the adjacent sectors that differ in most of a crown (the sector above is different from its adjacent neighbors) more internal.
I've tried some algorithms such as using simple combinations but it doesn´t work because it's a circle so the last color set has to match with the first one.
As far as I understand it, this question asks for an algorithm to generate a cyclic k-ary Gray code of length n. (I'm assuming that the intent is that m always be exactly kn so that all possible colour sequences are present in the circle. See below for a note about how to deal with finding shorter Gray sequences.)
A Gray code is an encoding system where consecutive codes have Hamming distance 1; that is, they differ in only one position. While the most usual Gray code is binary, the concept and the algorithm can easily be extended to base k for any k.
The classic binary Gray code is formed from a binary number by cumulatively XORing digits from "left to right" (i.e. high-order digit first). The following algorithm, copied without modification from Wikipedia, replaces the XOR with "sum modulo k"; that works also if k is 2 because XOR is exactly the modulo 2 sum of its arguments. [Notes 1 and 2]
I added a driver program which print out the kn distinct sequences for any n-length sequence of k colours, repeating the first line so as to make it clear that it is cyclic.
Actually, it is easy to prove that the last sequence differs in only one position from the first sequence, since the result of applying the algorithm to kn−1, which is the base-k number consisting entirely of the digit k−1, has a 0 in every position other than the first position.
// 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;
}
Here are some sample runs of this code:
./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
Now, to briefly consider the case where it is desired to produce an incomplete Gray sequence of length m < kn. I'll assume here that k>2 because for k=2, not all values of m have solutions. (In particular, if k is 2 and m is odd, there is no solution; this can be proven with a simple parity argument.)
First, suppose m ≥ 2kn−1.
I'll call an element in the Gray sequence final if it differs from both its predecessor and its sucessor only in the final position. It can be seen that final elements appear in runs of length k−2, separated by pairs of non-final elements. A final element can be deleted, because its predecessor and its successor must also differ from each other only in their final position. There are 2kn−1 non-final elements, and if m ≥ 2kn−1 we can remove kn−m final elements and still have a Gray sequence. This subsequence can be generated by with a filter which passes:
The second case are values of m which are even and less than k'×kn−1, where k' is the largest even number not greater than k. (That is, k' is k if k is even, and k−1 if k is odd.) In that case, we can make use of a subsequence of a reflected Gray code. Specifically, we use a Gray sequence for the mixed-base number whose digit weights are k' for the high-order digit position and k for all other digits. We start with the sequences:
Now, we define the sequence S as follows:
x prepended to every element).It should be clear that the i-th element from the beginning of S and the i-th element from the end of S differ only in their first digit. Consequently, we can use S to produce a Gray sequence of length 2i for any i up to k'/2.
Finally, if we need the sequence of length m where m is odd and less than k'×kn−1, we can use the above construct, leaving out the second element in the sequence.
The code puts the high-order digit in the last position in the array, so the "number" is effectively printed low-order digit first. That doesn't change anything important, although in retrospect I would have been better off printing the sequences backwards.
The Wikipedia edit history shows that the cited code is under dispute. In case it disappears again, I put a timestamped (i.e. permanent) URL in a comment in the code.