假設我們有兩個變數 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）
我需要一個非遞回函式或方法（在數學或編程中）從使用該規則設定的 L、S 中獲取第 i 個狀態（每次索引更改時更改一次）
uj5u.com熱心網友回復：
看來，您正在尋找格雷碼
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
uj5u.com熱心網友回復：
數學
可能有多個答案，我在另一個答案中看到格雷碼，但這是我自己的解決方案。示例以小數 (S=10) 給出，因為我認為小數比二進制更容易理解。但該方法適用于任何 S 值。
對于 2 位小數（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
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/415341.html
標籤：