生成列表的所有排列而不包含相邻的相等元素

当我们对列表进行sorting时，就像

a = [1,2,3,3,2,2,1] sorted(a) => [1, 1, 2, 2, 2, 3, 3] 

在结果列表中，相等的元素总是相邻的。

我怎样才能完成相反的任务 – 对列表进行洗牌，以便相等的元素永远不会（或者很less）相邻。

例如，对于上面的列表可能的解决scheme之一是

 p = [1,3,2,3,2,1,2] 

更正式地，给定一个列表a ，生成一个置换p ，使对数p[i]==p[i+1]的数量最小。

由于列表很大，生成和筛选所有排列不是一个选项。

奖金的问题：如何有效地产生所有这样的排列？

这是我用来testing解决scheme的代码： https ： //gist.github.com/gebrkn/9f550094b3d24a35aebd

UPD：在这里select一个赢家是一个艰难的select，因为很多人发表了很好的答案。 @ VincentvanderWeele ， @ David Eisenstat ， @ Coady ， @ enrico.bacis和@srgrg提供了完美无缺地产生最佳排列的function。 @tobias_k和大卫也回答了奖金问题（产生所有排列）。 大卫的正确性certificate附加点。

来自@VincentvanderWeele的代码看起来是最快的。

Answer 1

这是Thijser目前不完整的伪码。 这个想法是采取其余项目types中最频繁的，除非刚刚被采取。 （另请参阅Coady对此algorithm的实现 。）

 import collections import heapq class Sentinel: pass def david_eisenstat(lst): counts = collections.Counter(lst) heap = [(-count, key) for key, count in counts.items()] heapq.heapify(heap) output = [] last = Sentinel() while heap: minuscount1, key1 = heapq.heappop(heap) if key1 != last or not heap: last = key1 minuscount1 += 1 else: minuscount2, key2 = heapq.heappop(heap) last = key2 minuscount2 += 1 if minuscount2 != 0: heapq.heappush(heap, (minuscount2, key2)) output.append(last) if minuscount1 != 0: heapq.heappush(heap, (minuscount1, key1)) return output 

正确性的certificate

对于两个项目types，计数k1和k2，如果k1 <k2，则最优解具有k2-k1-1个缺陷，如果k1 = k2则具有0个缺陷，如果k1> k2则具有k1-k2-1个缺陷。 这个例子很明显。 其他是对称的; less数元素的每个实例最多可以防止总共k1 + k2-1中的两个缺陷。

这贪婪algorithm通过以下逻辑返回最佳的解答。 如果扩展到最佳解决scheme，我们称前缀（部分解决scheme）是安全的 。 显然前缀是空的是安全的，如果一个安全的前缀是一个完整的解决scheme，那么这个解决scheme是最佳的。 只要感谢地指出每个贪婪的步骤都是安全的。

贪婪的步骤引入缺陷的唯一方法是只剩下一个项目types，在这种情况下，只有一种方法可以继续，这种方式是安全的。 否则，令P为刚刚考虑的步骤之前的（安全）前缀，设P'为前面的前缀，设S是扩展P的最优解。如果S延拓P'，则完成。 否则，令P'= Px和S = PQ和Q = yQ'，其中x和y是项目，Q和Q'是序列。

首先假设P不以y结尾。 通过algorithm的select，x在Q中至less与y一样频繁。 考虑只包含x和y的Q的最大子串。 如果第一个子string的x至less和y一样多，那么它可以被重写，而不会引入额外的以x开头的缺陷。 如果第一个子string比y更多，那么其他一些子string比y更多，我们可以重写这些子string而没有额外的缺陷，所以x先行。 在这两种情况下，我们都可以根据需要find扩展P'的最佳解决schemeT.

现在假设P以y结束。 通过将第一次出现的x移动到前面来修改Q. 在这样做的时候，我们引入至多一个缺陷（x曾经是）并消除一个缺陷（yy）。

生成所有解决scheme

这是tobias_k的回答，加上有效的testing来检测当前正在考虑的select是否受到全局约束。 由于生成的开销在输出长度的数量级上，因此渐近运行时间是最优的。 不幸的是，最糟糕的延误是二次的; 可以通过更好的数据结构将其降低到线性（最佳）。

 from collections import Counter from itertools import permutations from operator import itemgetter from random import randrange def get_mode(count): return max(count.items(), key=itemgetter(1))[0] def enum2(prefix, x, count, total, mode): prefix.append(x) count_x = count[x] if count_x == 1: del count[x] else: count[x] = count_x - 1 yield from enum1(prefix, count, total - 1, mode) count[x] = count_x del prefix[-1] def enum1(prefix, count, total, mode): if total == 0: yield tuple(prefix) return if count[mode] * 2 - 1 >= total and [mode] != prefix[-1:]: yield from enum2(prefix, mode, count, total, mode) else: defect_okay = not prefix or count[prefix[-1]] * 2 > total mode = get_mode(count) for x in list(count.keys()): if defect_okay or [x] != prefix[-1:]: yield from enum2(prefix, x, count, total, mode) def enum(seq): count = Counter(seq) if count: yield from enum1([], count, sum(count.values()), get_mode(count)) else: yield () def defects(lst): return sum(lst[i - 1] == lst[i] for i in range(1, len(lst))) def test(lst): perms = set(permutations(lst)) opt = min(map(defects, perms)) slow = {perm for perm in perms if defects(perm) == opt} fast = set(enum(lst)) print(lst, fast, slow) assert slow == fast for r in range(10000): test([randrange(3) for i in range(randrange(6))]) 

Answer 2

伪代码：

1. sorting列表
2. 遍历sorting列表的前半部分，并填充结果列表的所有偶数索引
3. 遍历sorting列表的后半部分，并填充结果列表的所有奇数索引

如果超过一半的input由相同的元素组成，那么只有p[i]==p[i+1] ，在这种情况下，除了将相同的元素放在连续的点（通过皮壳孔原理）。

---

正如在评论中指出的那样，这种方法在一个元素出现至lessn/2次（或者对于奇数n n/2+1 ;这概括为(n+1)/2)为偶数和奇数）。 至多有两个这样的元素，如果有两个，algorithm工作得很好。 唯一有问题的情况是，至less有一半的时间出现一个元素。 我们可以简单地通过find元素并首先处理它来解决这个问题。

我不知道python写得不够好，所以我冒昧地从github上复制了OP的一个早期版本的实现：

 # Sort the list a = sorted(lst) # Put the element occurring more than half of the times in front (if needed) n = len(a) m = (n + 1) // 2 for i in range(n - m + 1): if a[i] == a[i + m - 1]: a = a[i:] + a[:i] break result = [None] * n # Loop over the first half of the sorted list and fill all even indices of the result list for i, elt in enumerate(a[:m]): result[2*i] = elt # Loop over the second half of the sorted list and fill all odd indices of the result list for i, elt in enumerate(a[m:]): result[2*i+1] = elt return result 

Answer 3

已经给出的最不常用的algorithm是不正确的。 这里有一个简单的实现，它最佳地使用堆来跟踪最常见的。

 import collections, heapq def nonadjacent(keys): heap = [(-count, key) for key, count in collections.Counter(a).items()] heapq.heapify(heap) count, key = 0, None while heap: count, key = heapq.heapreplace(heap, (count, key)) if count else heapq.heappop(heap) yield key count += 1 for index in xrange(-count): yield key >>> a = [1,2,3,3,2,2,1] >>> list(nonadjacent(a)) [2, 1, 2, 3, 1, 2, 3] 

Answer 4

您可以使用recursion回溯algorithm生成所有 “完全未sorting”的排列（在相邻位置没有两个相等的元素）。 事实上，产生所有排列的唯一区别是你跟踪最后一个数字，并排除一些相应的解决scheme：

 def unsort(lst, last=None): if lst: for i, e in enumerate(lst): if e != last: for perm in unsort(lst[:i] + lst[i+1:], e): yield [e] + perm else: yield [] 

请注意，在这种forms下，函数效率不高，因为它创build了许多子列表。 另外，我们可以通过首先查看最受限制的数字（计数最高的那些数字）来加快速度。 这是一个更有效的版本，只使用数字的counts 。

 def unsort_generator(lst, sort=False): counts = collections.Counter(lst) def unsort_inner(remaining, last=None): if remaining > 0: # most-constrained first, or sorted for pretty-printing? items = sorted(counts.items()) if sort else counts.most_common() for n, c in items: if n != last and c > 0: counts[n] -= 1 # update counts for perm in unsort_inner(remaining - 1, n): yield [n] + perm counts[n] += 1 # revert counts else: yield [] return unsort_inner(len(lst)) 

你可以用它来产生next完美的排列，或者是一个包含所有排列的list 。 但是请注意，如果没有完全sorting的sorting，那么这个生成器将不会产生任何结果。

 >>> lst = [1,2,3,3,2,2,1] >>> next(unsort_generator(lst)) [2, 1, 2, 3, 1, 2, 3] >>> list(unsort_generator(lst, sort=True)) [[1, 2, 1, 2, 3, 2, 3], ... 36 more ... [3, 2, 3, 2, 1, 2, 1]] >>> next(unsort_generator([1,1,1])) Traceback (most recent call last): File "<stdin>", line 1, in <module> StopIteration 

为了避免这个问题，可以将其与其他答案中提出的其中一种algorithm一起用作后备。 这将保证返回一个完美的未sorting的排列，如果有的话，或者一个好的近似。

 def unsort_safe(lst): try: return next(unsort_generator(lst)) except StopIteration: return unsort_fallback(lst) 

Answer 5

在Python中，你可以做到以下几点。

考虑你有一个sorting列表l ，你可以这样做：

 length = len(l) odd_ind = length%2 odd_half = (length - odd_ind)/2 for i in range(odd_half)[::2]: my_list[i], my_list[odd_half+odd_ind+i] = my_list[odd_half+odd_ind+i], my_list[i] 

这些只是就地操作，因此应该相当快（ O(N) ）。 请注意，您将从l[i] == l[i+1]为l[i] == l[i+2]所以您最终的顺序不是随机的，而是从我如何理解问题这不是你正在寻找的随机性。

这个想法是在中间拆分sorting列表，然后交换两部分中的其他元素。

对于l= [1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5]这导致l = [3, 1, 4, 2, 5, 1, 3, 1, 4, 2, 5]

一旦一个元素的丰度大于或等于列表长度的一半，该方法就不能摆脱所有的l[i] == l[i + 1] 。

虽然上面的工作正常，只要最频繁元素的丰度小于列表大小的一半， 下面的函数也处理极限情况 （着名的逐一问题），其中每一个以第一个必须是最丰富的一个：

 def no_adjacent(my_list): my_list.sort() length = len(my_list) odd_ind = length%2 odd_half = (length - odd_ind)/2 for i in range(odd_half)[::2]: my_list[i], my_list[odd_half+odd_ind+i] = my_list[odd_half+odd_ind+i], my_list[i] #this is just for the limit case where the abundance of the most frequent is half of the list length if max([my_list.count(val) for val in set(my_list)]) + 1 - odd_ind > odd_half: max_val = my_list[0] max_count = my_list.count(max_val) for val in set(my_list): if my_list.count(val) > max_count: max_val = val max_count = my_list.count(max_val) while max_val in my_list: my_list.remove(max_val) out = [max_val] max_count -= 1 for val in my_list: out.append(val) if max_count: out.append(max_val) max_count -= 1 if max_count: print 'this is not working' return my_list #raise Exception('not possible') return out else: return my_list 

Answer 6

这是一个很好的algorithm：

1. 首先要计算所有数字的频率。 把答案放在地图上。

2. 对这张地图进行sorting，以便最常出现的数字排在第一位。

3. 答案的第一个数字是sorting映射中的第一个数字。

4. 用现在的第一个小地图来度假地图。

如果你想提高效率，寻找方法来提高分拣步骤的效率。

Answer 7

这个想法是将元素从最常见到最不常见，最常用的元素进行sorting，减less它的数量，并按照降序排列在列表中（但是避免把最后使用的元素放在最前面以防止重复） 。

这可以使用Counter和bisect来实现：

 from collections import Counter from bisect import bisect def unsorted(lst): # use elements (-count, item) so bisect will put biggest counts first items = [(-count, item) for item, count in Counter(lst).most_common()] result = [] while items: count, item = items.pop(0) result.append(item) if count != -1: element = (count + 1, item) index = bisect(items, element) # prevent insertion in position 0 if there are other items items.insert(index or (1 if items else 0), element) return result 

例

 >>> print unsorted([1, 1, 1, 2, 3, 3, 2, 2, 1]) [1, 2, 1, 2, 1, 3, 1, 2, 3] >>> print unsorted([1, 2, 3, 2, 3, 2, 2]) [2, 3, 2, 1, 2, 3, 2] 

Answer 8

回答奖金问题：这是一个algorithm，它可以find一个集合中所有相邻元素不能相同的排列。 我相信这是在概念上最有效的algorithm（尽pipe其他人可能在实践中更快，因为它们转化为更简单的代码）。 它不使用暴力，它只产生独特的排列，并且不会导致解决scheme的path在最早的时候被切断。

我将使用“丰富的元素”一词作为一个集合中比所有其他元素组合更频繁的元素，而丰富元素的数量减去其他元素的数量。
例如设置的abac没有丰富的元素，设置abac和aabcaa具有丰富的元素和丰富的元素1和2。

1. 从一组开始：

aaabbcd

2. 从重复中分出第一个出现：

第一：abcd
重复：aab

3. 找出重复中丰富的元素，如果有的话，并计算丰度：

丰富的元素：a
丰富：1

4. 生成丰富元素之后的元素数量不less于丰度的所有第一个排列：（因此在这个例子中，“a”不能是最后一个）

abcd，abdc，acbd，acdb，adbc，adcb，bacd，badc，bcad， bcda ，bdac， bdca ，
cabd，cadb，cbad， cbda ，cdab， cdba ，dabc，dacb，abac， dbca ，dcab， dcba

5. 对于每个排列，请按照以下规则逐个插入一组重复字符：

5.1。 如果该集合的丰度大于排列中最后一次发生丰富元素之后的元素数目，则跳到下一个排列。
例如，当排列为abc ，如果丰度等于或小于2，则只能插入a元素a的集合，所以aaaabc可以， aaaaabc不可以。

5.2。 从排列中最后一次出现的集合中select元素。
例如，当排列是abcba并且设置为ab ，请selectb

5.3。 将所选元素插入排列中最后一次出现的右侧至less2个位置。
例如，当将b插入到置换babca ，结果是babcba和babcab

5.4。 执行第5步每个sorting和其余的集合。

 EXAMPLE: set = abcaba firsts = abc repeats = aab perm3 set select perm4 set select perm5 set select perm6 abc aab a abac ab b ababc aa ababac ababca abacb aa abacab abacba abca ab b abcba a - abcab aa abcaba acb aab a acab ab a acaba bb acabab acba ab b acbab aa acbaba bac aab b babc aa a babac aa babaca babca a - bacb aa a bacab aa bacaba bacba a - bca aab - cab aab a caba ab b cabab aa cababa cba aab - 

该algorithm生成独特的排列。 如果您想知道排列的总数（ aba因为可以切换a而被计数两次），请将唯一排列的数目乘以一个因子：

F = N ₁ ！ * N ₂ ！ * … * N _n ！

其中N是集合中每个元素的出现次数。 对于一套abcdabcaba这将是4！ * 3！ * 2！ * 1！ 或288，这表明algorithm是多么低效的产生所有排列而不是唯一的排列。 要列出在这种情况下的所有排列，只列出288次独特的排列:-)

下面是Javascript中的一个（相当笨拙的）实现; 我怀疑像Python这样的语言可能更适合这种事情。 运行代码片段来计算“abracadabra”的分离排列。

 // FIND ALL PERMUTATONS OF A SET WHERE NO ADJACENT ELEMENTS ARE IDENTICAL function seperatedPermutations(set) { var unique = 0, factor = 1, firsts = [], repeats = [], abund; seperateRepeats(set); abund = abundance(repeats); permutateFirsts([], firsts); alert("Permutations of [" + set + "]\ntotal: " + (unique * factor) + ", unique: " + unique); // SEPERATE REPEATED CHARACTERS AND CALCULATE TOTAL/UNIQUE RATIO function seperateRepeats(set) { for (var i = 0; i < set.length; i++) { var first, elem = set[i]; if (firsts.indexOf(elem) == -1) firsts.push(elem) else if ((first = repeats.indexOf(elem)) == -1) { repeats.push(elem); factor *= 2; } else { repeats.splice(first, 0, elem); factor *= repeats.lastIndexOf(elem) - first + 2; } } } // FIND ALL PERMUTATIONS OF THE FIRSTS USING RECURSION function permutateFirsts(perm, set) { if (set.length > 0) { for (var i = 0; i < set.length; i++) { var s = set.slice(); var e = s.splice(i, 1); if (e[0] == abund.elem && s.length < abund.num) continue; permutateFirsts(perm.concat(e), s, abund); } } else if (repeats.length > 0) { insertRepeats(perm, repeats); } else { document.write(perm + "<BR>"); ++unique; } } // INSERT REPEATS INTO THE PERMUTATIONS USING RECURSION function insertRepeats(perm, set) { var abund = abundance(set); if (perm.length - perm.lastIndexOf(abund.elem) > abund.num) { var sel = selectElement(perm, set); var s = set.slice(); var elem = s.splice(sel, 1)[0]; for (var i = perm.lastIndexOf(elem) + 2; i <= perm.length; i++) { var p = perm.slice(); p.splice(i, 0, elem); if (set.length == 1) { document.write(p + "<BR>"); ++unique; } else { insertRepeats(p, s); } } } } // SELECT THE ELEMENT FROM THE SET WHOSE LAST OCCURANCE IN THE PERMUTATION COMES FIRST function selectElement(perm, set) { var sel, pos, min = perm.length; for (var i = 0; i < set.length; i++) { pos = perm.lastIndexOf(set[i]); if (pos < min) { min = pos; sel = i; } } return(sel); } // FIND ABUNDANT ELEMENT AND ABUNDANCE NUMBER function abundance(set) { if (set.length == 0) return ({elem: null, num: 0}); var elem = set[0], max = 1, num = 1; for (var i = 1; i < set.length; i++) { if (set[i] != set[i - 1]) num = 1 else if (++num > max) { max = num; elem = set[i]; } } return ({elem: elem, num: 2 * max - set.length}); } } seperatedPermutations(["a","b","r","a","c","a","d","a","b","r","a"]); 

Answer 9

1. sorting列表。
2. 使用此algorithm生成列表的“最佳随机播放”

它会在列表中的最小项目（按项目值），因此它会尝试，例如，把1，2和3的sorting位置。

Answer 10

从长度为n的sorting列表开始。 令m = n / 2。 取值为0，然后是m，然后是1，然后是m + 1，然后是2，然后是m + 2，依此类推。 除非你有一半以上的数字是相同的，否则你将不会以连续的顺序获得相同的值。

Answer 11

请原谅我的“我也是”风格的答案，但是不能把科迪的答案简化为这个？

 from collections import Counter from heapq import heapify, heappop, heapreplace from itertools import repeat def srgerg(data): heap = [(-freq+1, value) for value, freq in Counter(data).items()] heapify(heap) freq = 0 while heap: freq, val = heapreplace(heap, (freq+1, val)) if freq else heappop(heap) yield val yield from repeat(val, -freq) 

编辑：这是一个Python 2版本，返回一个列表：

 def srgergpy2(data): heap = [(-freq+1, value) for value, freq in Counter(data).items()] heapify(heap) freq = 0 result = list() while heap: freq, val = heapreplace(heap, (freq+1, val)) if freq else heappop(heap) result.append(val) result.extend(repeat(val, -freq)) return result 

Answer 12

1. 计数每个值出现的次数
2. 按照从最频繁到最不频繁的顺序select值
3. 将所选值添加到最终输出中，每次将索引增加2
4. 如果索引超出范围，则将索引重置为1

 from heapq import heapify, heappop def distribute(values): counts = defaultdict(int) for value in values: counts[value] += 1 counts = [(-count, key) for key, count in counts.iteritems()] heapify(counts) index = 0 length = len(values) distributed = [None] * length while counts: count, value = heappop(counts) for _ in xrange(-count): distributed[index] = value index = index + 2 if index + 2 < length else 1 return distributed