我想枚举一个 n 元组。例如对于 n=2：
00 01 10 11
02 20 12 21 22
03 30 13 31 23 32 33
04 40 14 41 ...
n=3 会这样开始：
000 001 010 100 011 101 110 111
002 020 200 012 102 021 120 201 210 112 121 211 122 212 221 222
003 ...
具有相同元素的元组的顺序并不重要（例如 001 和 010），但具有更多（011 对 001）或更重要的更大（002 对 001）元素的元组应该总是在后面出现。
经过一番搜索，似乎有很多相关的算法，但没有一个专门针对这种情况。有这样的算法吗？
编辑： n=2 案例的图像。绿线表示通过打乱元组中元素的顺序到达的元素。
编辑：关于订单的说明：
让每个条目seq(n, k)产生您想要的k数字序列，数字从0到n。
让 stepi是生成最大位数为 的所有元组的阶段i。
在每一步，我们简单地生成i+1所有数字的 -ary 表示(i+1) ** (k - 1) - 1（即最多k-1位数）。对于每个-ary 表示，然后我们通过在-ary 表示中的每个位置i+1插入数字来生成序列的元素。ii+1
为了避免重复，我们会在遇到i已经存在于i+1-ary 表示中的情况下提前中断。
这是python中的（丑陋！）示例实现：
def to_nary_string(num, n):
if num == 0:
return "0"
result = ""
while num != 0:
result = str(num % n) + result
num /= n
return result
def seq(n, k):
print "0" * k
for i in range(2, n+2):
for x in range(i**(k-1)):
stem = to_nary_string(x, i).zfill(k-1)
c = str(i-1)
for j in range(k):
print stem[:j] + c + stem[j:],
if j != k-1 and stem[j] == c:
break
print
编辑：这个问题是k-1数字字符串必须与元组的顺序相同，而不是顺序n-ary 顺序。稍微改变函数会得到想要的结果：
# Original list and string version
def seq(n, k):
if (k == 0):
return [""]
result = []
for i in range(n+1):
c = str(hex(i))[2:] # 10 -> a, 11-> b, etc.
for subseq in seq(i, k-1):
for j in range(k):
result.append(subseq[:j] + c + subseq[j:])
if j != k-1 and subseq[j] == c:
break
return result
另外，感谢 Claudiu，这里有一个生成器和元组版本
# Generator and tuple version
#
# Thanks Claudiu!
def seq(n, k):
if (k == 0):
yield ()
return
for i in range(n+1):
for subseq in seq(i, k-1):
for j in range(k):
yield subseq[:j] + (i,) + subseq[j:]
if j != k-1 and subseq[j] == i:
break
结果（为清楚起见添加了换行符）：
>>> for x in seq(4, 2):
print x,
00
10 01 11
20 02 21 12 22
30 03 31 13 32 23 33
40 04 41 14 42 24 43 34 44
>>> for x in seq(3, 3):
print x,
000
100 010 001
110 101 011
111
200 020 002
210 120 102 201 021 012
211 121 112
220 202 022
221 212 122
222
300 030 003
310 130 103 301 031 013
311 131 113
320 230 203 302 032 023
321 231 213 312 132 123
322 232 223
330 303 033
331 313 133
332 323 233
333
并进行快速的健全性检查：
>>> len(seq(12, 4)) == 13 ** 4
True
编辑：您的编辑使此订购无效。留在这里留给后人。
这是我用英语实现的算法。基本上，为了获得您想要的排序，将问题视为“生成具有至少一个给定最大元素的所有 n 元组”。假设我们有这个，我们所要做的就是：
- yield `n` zeroes
- for each element greater than zero:
- yield all the n-tuples with at least one of that element
为了生成具有至少一个给定最大元素的所有 n 元组，我生成了该元素可能位于的所有可能位置 - 例如，对于 3 元组，这些位置将是
no no yes
no yes no
no yes yes
yes no no
yes no yes
yes yes no
yes yes yes
n这只是（是，否）选择的笛卡尔积。对于每个可能的位置，我们填写所有可能no的 s。什么可以进入nos？任何小于最大元素的元素。所以要做到这一点，你需要所有小于最大值（包括零）的元素的笛卡尔积，x乘以sx的数量no，并填写这些空白。因此，如果您有最大的 el3并且位置是，no no yes那么您可以这样做：
0 0 3
0 1 3
0 2 3
1 0 3
1 1 3
1 2 3
2 0 3
2 1 3
2 2 3
这是该算法的python实现：
import itertools
alphabet = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
def enumerate_n_tuples(n):
#the zero case:
yield [alphabet[0],]*n
for i in xrange(1, len(alphabet)):
#alphabet[i] is the largest element
#it must be present in the result
largest_el = alphabet[i]
#fill in the largest element in all possible combinations
for largest_el_map in itertools.product(*([(False,True)]*n)):
#other spots are filled freely up to (not including) largest
num_others = sum(1 for largest in largest_el_map
if not largest)
if num_others == n: continue #need at least one largest el
for others in itertools.product(*([alphabet[:i]]*num_others)):
#init the result to zeroes
res = [alphabet[0]]*n
#fill in the largest elements, putting the other
#elements in between
others_i = 0
for j,largest in enumerate(largest_el_map):
if largest:
res[j] = largest_el
else:
res[j] = others[others_i]
others_i += 1
yield res
例子：
>>> for threetup in enumerate_n_tuples(3):
print threetup
if threetup[-1]==3: break
[0, 0, 0]
[0, 0, 1]
[0, 1, 0]
[0, 1, 1]
[1, 0, 0]
[1, 0, 1]
[1, 1, 0]
[1, 1, 1]
[0, 0, 2]
[0, 1, 2]
[1, 0, 2]
[1, 1, 2]
[0, 2, 0]
[0, 2, 1]
[1, 2, 0]
[1, 2, 1]
[0, 2, 2]
[1, 2, 2]
[2, 0, 0]
[2, 0, 1]
[2, 1, 0]
[2, 1, 1]
[2, 0, 2]
[2, 1, 2]
[2, 2, 0]
[2, 2, 1]
[2, 2, 2]
[0, 0, 3]
好的，鉴于您n最多为 4 并且您只有 13 个元素，这确实是最好的方法：
import itertools
alphabet = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
def tup_sort_key(t):
largest_el = max(t)
z = list(t)
z.sort(reverse=True)
return tuple(z)
def gen_all_n_tuples(n):
all_els = list(itertools.product(*([alphabet]*n)))
all_els.sort(key=tup_sort_key)
return all_els
简要说明：生成所有可能的元组，并简单地应用您想要的排序顺序（最大元素、第二大元素、第三大元素等）。对于 n=4，这需要不到 0.2 秒。
结果：
>>> print "\n".join(map(str, gen_all_n_tuples(3)))
(0, 0, 0)
(0, 0, 1)
(0, 1, 0)
(1, 0, 0)
(0, 1, 1)
(1, 0, 1)
(1, 1, 0)
(1, 1, 1)
(0, 0, 2)
(0, 2, 0)
(2, 0, 0)
(0, 1, 2)
(0, 2, 1)
(1, 0, 2)
(1, 2, 0)
(2, 0, 1)
(2, 1, 0)
(1, 1, 2)
(1, 2, 1)
(2, 1, 1)
(0, 2, 2)
(2, 0, 2)
(2, 2, 0)
(1, 2, 2)
(2, 1, 2)
(2, 2, 1)
(2, 2, 2)
(0, 0, 3)
(0, 3, 0)
(3, 0, 0)
(0, 1, 3)
(0, 3, 1)
(1, 0, 3)
(1, 3, 0)
(3, 0, 1)
(3, 1, 0)
(1, 1, 3)
(1, 3, 1)
(3, 1, 1)
(0, 2, 3)
(0, 3, 2)
etc...
This algorithm generates the next element that satisfies your constraints.
generateNext(int a[1:m]) {
Let n be the largest number in a.
IF a[i] == n for all i: { // e.g. If a = 111
set a[1] = n+1 and a[j] = 0 for all j in 2 to m.
return
}
ELSE {
Let p be the last position where n appears.
IF a[i] == n for all i to the left of p { // trivially true when p is 1.
set a[i] = 0 for all i to the left of p.
IF a[i] == n-1 for all i to the right of p { // trivially true when p is m.
set a[i] = 0 for all i to the right of p.
set a[p-1] = n
}
ELSE {
generateNext(a[p+1:m])
seta[i] = 0 for all i to the left of p
}
}
ELSE
generateNext(a[1:p-1])
}
}
当使用 002 调用时，算法返回的数字序列应为：002 012 102 112 022 122 202 212 222 020 120 220 021 121 221 200 201 210 211
作为参考，veredesmarald 对 Claudiu 的 C# 实现的回答的一个端口。Python 的数组肯定更简洁。
public IEnumerable<List<int>> Enumerate (int n, int k)
{
if (k == 0) {
yield return new List<int> ();
yield break;
}
yield return Enumerable.Repeat (0, k).ToList ();
for (int i = 1; i <= n; i++) {
foreach (var x in Enumerate (i, k - 1)) {
for (int j = 0; j < k; j++) {
var res = x.Take (j).Concat (new int[] { i }).Concat (x.Skip (j));
yield return res.ToList ();
if (j != k - 1 && x[j] == i) {
break;
}
}
}
}
}
public IEnumerable<List<int>> Enumerate (int k)
{
return Enumerate (int.MaxValue, k);
}
// Test:
foreach (var tuple in Enumerate (3).Take (100)) {
Console.Write (string.Concat (tuple.Select (x => x.ToString ())) + " ");
if (tuple.All (x => x == tuple[0])) {
Console.WriteLine ();
}
}