geo*_*org 86 python algorithm combinatorics
当我们对列表进行排序时,比如
a = [1,2,3,3,2,2,1]
sorted(a) => [1, 1, 2, 2, 2, 3, 3]
等值元素在结果列表中始终相邻.
我怎样才能完成相反的任务 - 对列表进行洗牌,使相邻的元素永远(或尽可能不相邻)相邻？
例如,对于上面的列表,可能的解决方案之一是
p = [1,3,2,3,2,1,2]
更正式地说,给定一个列表a,生成一个p最小化对的数量的排列p[i]==p[i+1].
由于列表很大,因此不能生成和过滤所有排列.
奖金问题:如何有效地生成所有这些排列？
这是我用来测试解决方案的代码:https://gist.github.com/gebrkn/9f550094b3d24a35aebd
UPD:在这里选择获胜者是一个艰难的选择,因为许多人发布了很好的答案.@VincentvanderWeele,@大卫Eisenstat,@Coady,@ enrico.bacis和@srgerg提供函数完美产生的最佳可能的排列.@tobias_k和大卫也回答了红利问题(生成所有排列).大卫的其他要点是正确性证明.
来自@VincentvanderWeele的代码似乎是最快的.
Dav*_*tat 30
这与Thijser当前不完整的伪代码一致.除非刚刚采用,否则我们的想法是采用最常见的剩余项目类型.(另请参阅Coady对此算法的实现.)
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
对于具有计数k1和k2的两个项类型,如果k1 <k2,则最优解具有k2-k1-1个缺陷,如果k1 = k2则为0个缺陷,并且如果k1> k2则为k1-k2-1个缺陷.=的情况很明显.其他是对称的; 少数元素的每个实例最多可以防止总共k1 + k2-1中的两个缺陷.
这种贪心算法通过以下逻辑返回最优解.如果扩展到最佳解决方案,我们称前缀(部分解决方案)是安全的.显然,空前缀是安全的,如果安全前缀是一个完整的解决方案,那么该解决方案是最佳的.足以以感应方式显示每个贪婪步骤都能保持安全.
贪婪步骤引入缺陷的唯一方法是,如果只剩下一种项目类型,在这种情况下只有一种方法可以继续,这种方式是安全的.否则,让P成为正在考虑的步骤之前的(安全)前缀,让P'成为之后的前缀,并且让S成为扩展P的最优解.如果S也扩展P',那么我们就完成了.否则,令P'= Px并且S = PQ且Q = yQ',其中x和y是项,Q和Q'是序列.
首先假设P不以y结尾.通过算法的选择,x在Q中至少与y一样频繁.考虑仅包含x和y的Q的最大子串.如果第一个子字符串的y至少与y的x一样多,则可以重写它,而不会引入以x开头的其他缺陷.如果第一个子字符串的y比x更多,那么其他一些子字符串的x比y更多,我们可以重写这些子字符串而不会有其他缺陷,因此x首先出现.在这两种情况下,我们根据需要找到扩展P'的最优解T.
现在假设P以y结尾.通过将第一次出现的x移到前面来修改Q. 在这样做时,我们最多引入一个缺陷(x曾经是x)并消除一个缺陷(yy).
这是tobias_k的答案以及有效的测试,以检测当前正在考虑的选择何时以某种方式受到全局约束.渐近运行时间是最优的,因为生成的开销是输出长度的量级.不幸的是,最坏情况的延迟是二次的; 它可以通过更好的数据结构简化为线性(最佳).
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))])
Vin*_*ele 22
伪代码:
只有p[i]==p[i+1]当输入的一半以上由相同的元素组成时,才会有这种情况,在这种情况下除了将相同的元素放在连续的点(通过皮江孔原理)之外别无选择.
正如评论中所指出的,这种方法可能有一个冲突太多,以防其中一个元素至少出现n/2一次(或者n/2+1对于奇数n;这可以推广到(n+1)/2)偶数和奇数).最多有两个这样的元素,如果有两个,算法运行得很好.唯一有问题的情况是,有一个元素至少有一半时间出现.我们可以通过找到元素并首先处理它来简单地解决这个问题.
我不太了解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
A. *_*ady 10
已经给出的最左边的最常见项目的算法是正确的.这是一个简单的实现,它最佳地使用堆来跟踪最常见的.
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]
您可以使用递归回溯算法生成所有 "完全未排序"的排列(在相邻位置中没有两个相等的元素).实际上,生成所有排列的唯一区别是您跟踪最后一个数字并相应地排除一些解决方案:
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 []
请注意,在这种形式下,函数效率不高,因为它创建了许多子列表.此外,我们可以通过首先查看最受约束的数字(具有最高计数的数字)来加快速度.这是一个使用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保持所有排列.但请注意,如果没有完全未排序的排列,则此生成器将因此不会产生任何结果.
>>> 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
为了避免这个问题,您可以将其与其他答案中提出的算法之一一起用作后备.这将保证返回完全未排序的排列(如果有的话)或其他方面的良好近似.
def unsort_safe(lst):
try:
return next(unsort_generator(lst))
except StopIteration:
return unsort_fallback(lst)
在python中,您可以执行以下操作.
考虑你有一个排序列表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]所以您最终得到的顺序是随机的,但从我如何理解这个问题来看,它不是您正在寻找的随机性.
我们的想法是在中间拆分排序列表,然后交换这两部分中的每个其他元素.
对于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
这是一个很好的算法:
首先计算所有数字的频率.将答案放在地图中.
对此地图进行排序,以便最常出现的数字首先出现.
您的答案的第一个数字是有序地图中的第一个数字.
度假地图的第一个现在是一个较小的.
如果您想提高效率,可以寻找提高分选步骤效率的方法.
在回答奖金问题时:这是一种算法,它找到一组中没有相邻元素可以相同的排列.我认为这是概念上最有效的算法(尽管其他算法在实践中可能更快,因为它们可以转换为更简单的代码).它不使用蛮力,它只产生独特的排列,并且最早点切断不能导致解决方案的路径.
我将对集合中的元素使用术语"丰富元素",其比所有其他元素组合更频繁地出现,并且对于丰富元素的数量减去其他元素的数量,术语"丰度".
例如,该集合abac没有丰富的元素,集合abaca并且aabcaa具有a丰富的元素,并且分别具有丰度1和2.
aaabbcd
第一:abcd
重复:aab
丰富的元素:
丰富:1
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.1.如果集合的丰度大于到目前为止在置换中丰富元素的最后一次出现之后的元素数量,则跳到下一个置换.
例如,当到目前为止的排列时abc,a如果丰度为2或更少,则只能插入具有丰富元素的集合,所以aaaabc可以,aaaaabc不是.5.2.从集合中的最后一次出现的元素中选择元素.
例如,当到目前为止的排列abcba和设置是ab,选择b5.3.将所选元素插入排列中最后一次出现的右侧至少2个位置.
例如,当插入b排列时babca,结果是babcba和babcab5.4.递归步骤5,每个结果排列和集合的其余部分.
EXAMPLE:
set = abcaba
firsts = abc
repeats = aab
perm3 set select perm4 set select perm5 set select perm6
abc aab a abac ab b ababc a a ababac
ababca
abacb a a abacab
abacba
abca ab b abcba a -
abcab a a abcaba
acb aab a acab ab a acaba b b acabab
acba ab b acbab a a acbaba
bac aab b babc aa a babac a a babaca
babca a -
bacb aa a bacab a a bacaba
bacba a -
bca aab -
cab aab a caba ab b cabab a a cababa
cba aab -
该算法生成唯一的排列.如果您想知道排列的总数(aba由于您可以切换a的位置,计算两次),请将唯一排列的数量乘以一个因子:
F = N 1!*N 2!*...*N n!
其中N是集合中每个元素的出现次数.对于一组abcdabcaba这将是4!*3!*2!*1!或者288,它表明算法是多么低效,它产生所有排列而不仅仅是唯一排列.要列出这种情况下的所有排列,只需列出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"]);