迭代所有可能的状态，只改变一次
Iterate over all possible states with only one change
假设我们有两个变量 L 和 S
L：任何序列的长度（任何序列中的项目数）
S：任何项目的可能状态数
假设我们有一组包含这两个变量的所有可能序列。
例如：
L=3, S=2
All Possible Sequences : S is 2 so we can have 0 and 1 for any item
0,1,0 0,0,0 1,0,0 1,1,0 1,1,1 0,1,1 0,0,1 1,0,1
现在我遇到的问题是：有没有办法通过每一步只改变一次来迭代所有可能序列的集合？你可以在我上面写的例子中看到一个例子。 （我已经手工计算了它们）。在每一步，我们只有一个变化（一项增加或减少1）
我需要一个 none 递归函数或方法（在数学或编程中）以从使用该规则设置的 L、S 中获取第 i 个状态（每次索引更改时更改一次）
看来，您正在寻找 Gray codes
C#代码
public static IEnumerable<int[]> GrayCodes(int length, int radix) {
if (length < 0)
throw new ArgumentOutOfRangeException(nameof(length));
if (radix < 0)
throw new ArgumentOutOfRangeException(nameof(radix));
if (0 == length || 0 == radix)
yield break;
static int digit(long n, int radix, int i) =>
(int)(Math.Floor(n / Math.Pow(radix, i)) % radix);
double count = Math.Pow(radix, length);
long max = count > long.MaxValue ? long.MaxValue : (long)count;
for (long i = 0; i < max; ++i) {
int[] result = new int[length];
int shift = 0;
for (int j = length - 1; j >= 0; j--) {
var x = (digit(i, radix, j) + shift) % radix;
shift += radix - x;
result[length - j - 1] = x;
}
yield return result;
}
}
演示
var report = string.Join(Environment.NewLine, GrayCodes(2, 3)
.Select(g => string.Join(" ", g)));
Console.Write(report);
结果：
0 0
0 1
0 2
1 2
1 0
1 1
2 1
2 2
2 0
如果要展平序列，请添加SelectMany:
var report = string.Join(", ", GrayCodes(2, 3).SelectMany(g => g));
Console.WriteLine(report);
Console.WriteLine();
// Your case, length = 3, radix = 2
report = string.Join(", ", GrayCodes(3, 2).SelectMany(g => g));
Console.WriteLine(report);
结果：
0, 0, 0, 1, 0, 2, 1, 2, 1, 0, 1, 1, 2, 1, 2, 2, 2, 0
0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0
编辑：如果“每一步只改变一次”意味着不仅是“在一个位置”（所以2 1 0 -> 2 1 2是允许的) 但在“在一个位置 和 仅按 +1 或 -1”，您仍然可以使用格雷码。该算法（让我将其命名为“To and Fro”）如下。
- 从零开始
0...000
- 开始 递增
nth 位可能：0..00 -> 0..01 -> .. -> 0..00dn
- 递增
n-1位并开始递减n位：0..00dn -> 0..01dn -> ... 0..011 -> 0..10
- 增加第
n-1位并开始递增n第0..10 -> 0..20 -> 0..021 -> ...0..2dn
- 在
0..0dn-1dn 递增第 n-2 个索引并开始递减第 n 个等
演示
# start from 000
000 -> 001 -> 002 ->
# increment n-1 th digit, decrementing n-th
-> 012 -> 011 -> 010 ->
# increment n-1 th digit, incrementing n-th
-> 020 -> 021 -> 022 ->
# increment n-2 th digit, decrementing n-th
-> 122 -> 121 -> 120 ->
# decrement n-1 th digit, incrementing n-th
-> 110 -> 111 -> 112 ->
# decrement n-1 th digit, decrementing n-th
-> 102 -> 101 -> 100 ->
# increment n-2 th digit, incrementing n-th
-> 200 -> 201 -> 202 ->
# increment n-1 th digit, decrementing n-th
-> 212 -> 211 -> 210 ->
# increment n-1 th digit, incrementing n-th
-> 220 -> 221 -> 222
C#代码：（拜托，fiddle）
public static IEnumerable<int[]> GrayCodes(int length, int radix) {
if (length < 0)
throw new ArgumentOutOfRangeException(nameof(length));
if (radix < 0)
throw new ArgumentOutOfRangeException(nameof(radix));
if (0 == length || 0 == radix)
yield break;
int[] signs = Enumerable.Repeat(1, length).ToArray();
int[] current = new int[length];
for (bool keep = true; keep; ) {
yield return current.ToArray();
keep = false;
for (int i = current.Length - 1; i >= 0; --i) {
int d = current[i] + signs[i];
if (d >= 0 && d < radix) {
current[i] = d;
for (int j = i + 1; j < signs.Length; ++j)
signs[j] = -signs[j];
keep = true;
break;
}
}
}
}
演示：
Console.Write(string.Join(Environment.NewLine, GrayCodes(3, 3)
.Select(line => string.Join(" ", line))));
结果：
0 0 0
0 0 1
0 0 2
0 1 2
0 1 1
0 1 0
0 2 0
0 2 1
0 2 2
1 2 2
1 2 1
1 2 0
1 1 0
1 1 1
1 1 2
1 0 2
1 0 1
1 0 0
2 0 0
2 0 1
2 0 2
2 1 2
2 1 1
2 1 0
2 2 0
2 2 1
2 2 2
数学
可能有多个答案，我在另一个答案中看到格雷码，但这是我自己的解决方案。示例以小数形式给出 (S=10)，因为我认为小数比二进制更容易理解。但是该方法适用于 S.
的任何值
对于两位小数（L=2，S=10），我可以有：
00, 01, 02, 03, ... 09, 19, 18, 17, 16, ... 10, 20, 21, 22, ...
也就是09之后，不是10，而是19，开始倒数18、17、……10，然后到20，重复：
20, ... 29, 39, ... 30, 40, ... 49, 59, ...
最终我们将达到 90：
30, 40, ... 50, 60, ... 70, 80, ... 90
但是我们不能达到 100，因为这涉及到 2 个数字被更改。但是我们可以使用相同的倒数技巧：
090, 190, 191, ... 199, 189, 188, ... 180, 170, 171, ... 179, 169, ...
函数
在Python。解释为代码中的注释。
def f(n, l, s):
# Get all digits of n.
# Example for decimals (s=10), if n = 143, digits = [1, 4, 3]
digits = []
cur_n = n
for i in range(l):
cur_digit = cur_n%s
digits.append(cur_digit)
cur_n = int(cur_n / s)
digits.reverse() # digits = [1, 4, 3]
# Continuing the same decimals example if n = 143, the output should be 153.
# Explanation below. We first copy the digits.
output_digits = list(digits)
# First digit is the same.
output_digits[0] = digits[0]
# For each digit
for i in range(len(digits) - 1):
digit=digits[i]
next_digit = digits[i+1]
# If it is an odd number
if digit%2 == 1:
# Then the next_output_digit is 9 - next_digit
next_output_digit = s - 1 - next_digit
else:
# Else, the next_output_digit is the same as next_digit
next_output_digit = next_digit
output_digits[i+1] = next_output_digit
# Convert [1, 5, 3] to ["1", "5", "3"]
output_digits_string = [str(digit) for digit in output_digits]
# Convert to "153"
output_string = "".join(output_digits_string)
# Finally, return output_string
return int(output_string)
为了测试算法，运行 这 2 个例子：
for i in range(199): print(f(i,3,10)) # Decimals, 3 digits, first 199 values
for i in range(8): print(f(i,3,2)) # Binaries, 3 digits, all 8 values
想法：
假设某个位置的每个数字每（从右到左）1、S、S * S、S * S * S ... 迭代更改一次。
每 2 * S 的变化都会根据 (0 ... S - 1, S - 1 ... 0):
0 -> 0
...
S - 1 -> S - 1
S -> S - 1
S + 1 -> S - 2
...
2 * S - 1 -> 0
由于S - 1 和S 产生相同的结果将保证当先前位置的数字发生变化时，数字保持不变。
C# 实现：
public static int[] Func(long n, int S, int L)
{
var num = new int[L];
for (int i = L - 1; i >= 0; i--)
{
var x = (int)(n % (2 * S));
num[i] = x < S ? x : 2 * S - x - 1;
n /= S;
}
return num;
}
遍历整个序列：
int S = 3, L = 3;
for (int i = 0; i < Math.Pow(S, L); i++)
{
Console.WriteLine(String.Join(' ', Func(i, S, L)));
}
输出：
0 0 0
0 0 1
0 0 2
0 1 2
0 1 1
0 1 0
0 2 0
0 2 1
0 2 2
1 2 2
1 2 1
1 2 0
1 1 0
1 1 1
1 1 2
1 0 2
1 0 1
1 0 0
2 0 0
2 0 1
2 0 2
2 1 2
2 1 1
2 1 0
2 2 0
2 2 1
2 2 2
可以在这里试试：https://dotnetfiddle.net/5AzYWr
假设我们有两个变量 L 和 S
L：任何序列的长度（任何序列中的项目数）
S：任何项目的可能状态数
假设我们有一组包含这两个变量的所有可能序列。 例如：
L=3, S=2
All Possible Sequences : S is 2 so we can have 0 and 1 for any item
0,1,0 0,0,0 1,0,0 1,1,0 1,1,1 0,1,1 0,0,1 1,0,1
现在我遇到的问题是：有没有办法通过每一步只改变一次来迭代所有可能序列的集合？你可以在我上面写的例子中看到一个例子。 （我已经手工计算了它们）。在每一步，我们只有一个变化（一项增加或减少1）
我需要一个 none 递归函数或方法（在数学或编程中）以从使用该规则设置的 L、S 中获取第 i 个状态（每次索引更改时更改一次）
看来，您正在寻找 Gray codes
C#代码
public static IEnumerable<int[]> GrayCodes(int length, int radix) {
if (length < 0)
throw new ArgumentOutOfRangeException(nameof(length));
if (radix < 0)
throw new ArgumentOutOfRangeException(nameof(radix));
if (0 == length || 0 == radix)
yield break;
static int digit(long n, int radix, int i) =>
(int)(Math.Floor(n / Math.Pow(radix, i)) % radix);
double count = Math.Pow(radix, length);
long max = count > long.MaxValue ? long.MaxValue : (long)count;
for (long i = 0; i < max; ++i) {
int[] result = new int[length];
int shift = 0;
for (int j = length - 1; j >= 0; j--) {
var x = (digit(i, radix, j) + shift) % radix;
shift += radix - x;
result[length - j - 1] = x;
}
yield return result;
}
}
演示
var report = string.Join(Environment.NewLine, GrayCodes(2, 3)
.Select(g => string.Join(" ", g)));
Console.Write(report);
结果：
0 0
0 1
0 2
1 2
1 0
1 1
2 1
2 2
2 0
如果要展平序列，请添加SelectMany:
var report = string.Join(", ", GrayCodes(2, 3).SelectMany(g => g));
Console.WriteLine(report);
Console.WriteLine();
// Your case, length = 3, radix = 2
report = string.Join(", ", GrayCodes(3, 2).SelectMany(g => g));
Console.WriteLine(report);
结果：
0, 0, 0, 1, 0, 2, 1, 2, 1, 0, 1, 1, 2, 1, 2, 2, 2, 0
0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0
编辑：如果“每一步只改变一次”意味着不仅是“在一个位置”（所以2 1 0 -> 2 1 2是允许的) 但在“在一个位置 和 仅按 +1 或 -1”，您仍然可以使用格雷码。该算法（让我将其命名为“To and Fro”）如下。
- 从零开始
0...000 - 开始 递增
nth 位可能：0..00 -> 0..01 -> .. -> 0..00dn - 递增
n-1位并开始递减n位：0..00dn -> 0..01dn -> ... 0..011 -> 0..10 - 增加第
n-1位并开始递增n第0..10 -> 0..20 -> 0..021 -> ...0..2dn - 在
0..0dn-1dn递增第n-2个索引并开始递减第n个等
演示
# start from 000
000 -> 001 -> 002 ->
# increment n-1 th digit, decrementing n-th
-> 012 -> 011 -> 010 ->
# increment n-1 th digit, incrementing n-th
-> 020 -> 021 -> 022 ->
# increment n-2 th digit, decrementing n-th
-> 122 -> 121 -> 120 ->
# decrement n-1 th digit, incrementing n-th
-> 110 -> 111 -> 112 ->
# decrement n-1 th digit, decrementing n-th
-> 102 -> 101 -> 100 ->
# increment n-2 th digit, incrementing n-th
-> 200 -> 201 -> 202 ->
# increment n-1 th digit, decrementing n-th
-> 212 -> 211 -> 210 ->
# increment n-1 th digit, incrementing n-th
-> 220 -> 221 -> 222
C#代码：（拜托，fiddle）
public static IEnumerable<int[]> GrayCodes(int length, int radix) {
if (length < 0)
throw new ArgumentOutOfRangeException(nameof(length));
if (radix < 0)
throw new ArgumentOutOfRangeException(nameof(radix));
if (0 == length || 0 == radix)
yield break;
int[] signs = Enumerable.Repeat(1, length).ToArray();
int[] current = new int[length];
for (bool keep = true; keep; ) {
yield return current.ToArray();
keep = false;
for (int i = current.Length - 1; i >= 0; --i) {
int d = current[i] + signs[i];
if (d >= 0 && d < radix) {
current[i] = d;
for (int j = i + 1; j < signs.Length; ++j)
signs[j] = -signs[j];
keep = true;
break;
}
}
}
}
演示：
Console.Write(string.Join(Environment.NewLine, GrayCodes(3, 3)
.Select(line => string.Join(" ", line))));
结果：
0 0 0
0 0 1
0 0 2
0 1 2
0 1 1
0 1 0
0 2 0
0 2 1
0 2 2
1 2 2
1 2 1
1 2 0
1 1 0
1 1 1
1 1 2
1 0 2
1 0 1
1 0 0
2 0 0
2 0 1
2 0 2
2 1 2
2 1 1
2 1 0
2 2 0
2 2 1
2 2 2
数学
可能有多个答案，我在另一个答案中看到格雷码，但这是我自己的解决方案。示例以小数形式给出 (S=10)，因为我认为小数比二进制更容易理解。但是该方法适用于 S.
的任何值对于两位小数（L=2，S=10），我可以有：
00, 01, 02, 03, ... 09, 19, 18, 17, 16, ... 10, 20, 21, 22, ...
也就是09之后，不是10，而是19，开始倒数18、17、……10，然后到20，重复：
20, ... 29, 39, ... 30, 40, ... 49, 59, ...
最终我们将达到 90： 30, 40, ... 50, 60, ... 70, 80, ... 90
但是我们不能达到 100，因为这涉及到 2 个数字被更改。但是我们可以使用相同的倒数技巧：
090, 190, 191, ... 199, 189, 188, ... 180, 170, 171, ... 179, 169, ...
函数
在Python。解释为代码中的注释。
def f(n, l, s):
# Get all digits of n.
# Example for decimals (s=10), if n = 143, digits = [1, 4, 3]
digits = []
cur_n = n
for i in range(l):
cur_digit = cur_n%s
digits.append(cur_digit)
cur_n = int(cur_n / s)
digits.reverse() # digits = [1, 4, 3]
# Continuing the same decimals example if n = 143, the output should be 153.
# Explanation below. We first copy the digits.
output_digits = list(digits)
# First digit is the same.
output_digits[0] = digits[0]
# For each digit
for i in range(len(digits) - 1):
digit=digits[i]
next_digit = digits[i+1]
# If it is an odd number
if digit%2 == 1:
# Then the next_output_digit is 9 - next_digit
next_output_digit = s - 1 - next_digit
else:
# Else, the next_output_digit is the same as next_digit
next_output_digit = next_digit
output_digits[i+1] = next_output_digit
# Convert [1, 5, 3] to ["1", "5", "3"]
output_digits_string = [str(digit) for digit in output_digits]
# Convert to "153"
output_string = "".join(output_digits_string)
# Finally, return output_string
return int(output_string)
为了测试算法，运行 这 2 个例子：
for i in range(199): print(f(i,3,10)) # Decimals, 3 digits, first 199 values
for i in range(8): print(f(i,3,2)) # Binaries, 3 digits, all 8 values
想法：
假设某个位置的每个数字每（从右到左）1、S、S * S、S * S * S ... 迭代更改一次。
每 2 * S 的变化都会根据 (0 ... S - 1, S - 1 ... 0):
0 -> 0
...
S - 1 -> S - 1
S -> S - 1
S + 1 -> S - 2
...
2 * S - 1 -> 0
由于S - 1 和S 产生相同的结果将保证当先前位置的数字发生变化时，数字保持不变。
C# 实现：
public static int[] Func(long n, int S, int L)
{
var num = new int[L];
for (int i = L - 1; i >= 0; i--)
{
var x = (int)(n % (2 * S));
num[i] = x < S ? x : 2 * S - x - 1;
n /= S;
}
return num;
}
遍历整个序列：
int S = 3, L = 3;
for (int i = 0; i < Math.Pow(S, L); i++)
{
Console.WriteLine(String.Join(' ', Func(i, S, L)));
}
输出：
0 0 0
0 0 1
0 0 2
0 1 2
0 1 1
0 1 0
0 2 0
0 2 1
0 2 2
1 2 2
1 2 1
1 2 0
1 1 0
1 1 1
1 1 2
1 0 2
1 0 1
1 0 0
2 0 0
2 0 1
2 0 2
2 1 2
2 1 1
2 1 0
2 2 0
2 2 1
2 2 2
可以在这里试试：https://dotnetfiddle.net/5AzYWr