algorithm - n 元组的平面排列(广度优先)

Question

我想枚举一个 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 案例的图像。绿线表示通过打乱元组中元素的顺序到达的元素。

编辑:关于订单的说明:

1. 元组主要按最大元素排序 (152 > 444)
2. 然后按它们的第二大元素排序 (053 > 252) 依此类推 (12341 > 12340)
3. 具有相同元素的元组之间的顺序是任意的(123 = 321)

Answer 1

让 seq(n, k) 产生你想要的序列，每个条目有 k 个数字，数字从 0 到 n.

设步骤i 是生成所有最大数字为i 的元组的阶段。

在每一步，我们简单地生成所有数字的 i+1 元表示，直到 (i+1) ** (k - 1) - 1(即最多 k-1 位)。对于每个 i+1 元表示，我们然后通过在 i+1 中的每个位置插入数字 i 来生成序列的元素>-ary 表示法。

为了避免重复，我们会在遇到 i+1 元表示中已经存在的 i 时提前中断。

这是 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