如何排序排列,使每个排列中至少有1个元素恰好相差1

Question

这篇文章提供了一些很好的python代码来查找一个总和为某个数字S的集合中的所有排列.我想消除输出中的不连续性,这样输出行中的任何一个元素都不会超过任何一个相邻的一排.

以下是生成我想要订购/排序的输出的代码:

def f(n,s):
    if n == 1:
        yield (s,)
    else:
        for i in xrange(s + 1):
            for j in f(n - 1,s - i):
                yield (i,) + j

L = list(f(3,5))

for i in L:
    print i

输出:

(0, 0, 5)
(0, 1, 4)
(0, 2, 3)
(0, 3, 2)
(0, 4, 1)
(0, 5, 0)
(1, 0, 4) <-Bad, 0 transitioned to 4 from one row to the next
(1, 1, 3)
(1, 2, 2)
(1, 3, 1) 
(1, 4, 0)
(2, 0, 3) <-Bad, 4 transitioned to 0 from one row to the next
(2, 1, 2)
(2, 2, 1)
(2, 3, 0)
(3, 0, 2)
(3, 1, 1)
(3, 2, 0)
(4, 0, 1) <-Bad, 2 transitioned to 0 from one row to the next
(4, 1, 0)
(5, 0, 0)

Desired Output:
(0, 0, 5)
(0, 1, 4)
(0, 2, 3)
(0, 3, 2)
(0, 4, 1)
(0, 5, 0)
(1, 4, 0)
(1, 3, 1) 
(1, 2, 2)
(1, 1, 3)
(1, 0, 4)
(2, 0, 3)
(2, 1, 2)
(2, 2, 1)
(2, 3, 0)
(3, 2, 0)
(3, 1, 1)
(3, 0, 2)
(4, 0, 1)
(4, 1, 0)
(5, 0, 0)

任何人都可以提出一些代码,以这种方式订购输出？

Answer 1

虽然可能不是最优雅的解决方案，但这是可行的：

def f(n, s):
    def g(n,s):
        if n == 1:
            yield (s,)
        else:
            for i in xrange(s + 1):
                for j in g(n - 1,s - i):
                    yield (i,) + j

    L = list(g(3, 5))

    D = []

    i = 1

    while i != len(L):
        for j in xrange(len(L[i])):
            if abs(L[i][j] - L[i-1][j]) > 1:
                D.append(L.pop(i))
                i -= 1
                break
        for d in D:
            ins = True
            for j in xrange(len(L[-1])):
                if abs(L[-1][j] - d[j]) > 1:
                    ins = False
                    break
            if ins:
                L.append(d)
                D.remove(d)
        i += 1

    return L

for i in f(3, 5):
    print i

这打印：

(0, 0, 5)
(0, 1, 4)
(0, 2, 3)
(0, 3, 2)
(0, 4, 1)
(0, 5, 0)
(1, 4, 0)
(2, 3, 0)
(3, 2, 0)
(4, 1, 0)
(5, 0, 0)
(4, 0, 1)
(3, 0, 2)
(2, 0, 3)
(1, 0, 4)
(1, 1, 3)
(2, 1, 2)
(3, 1, 1)
(2, 2, 1)
(1, 2, 2)
(1, 3, 1)

它基本上将,g内部定义f为创建排列的生成器。然后它会遍历该列表并检查每个元素是否abs第一个子列表中的元素与之前的元素之间的差异（部分）（没有很好地解释，我知道......但你明白了）大于 1，如果是，则删除该列表，将其附加到D并将索引减少 1（这就是我使用while而不是 的原因for）。

编辑： 每次检查元素后，它都会检查D并查看是否有任何内容适合L，如果适合，则将其附加。

然后它返回过滤后的列表。