为了账号安全,请及时绑定邮箱和手机立即绑定

生成列表的所有排列,而没有相邻的相等元素

生成列表的所有排列,而没有相邻的相等元素

慕娘9325324 2019-12-21 10:59:29
当我们对列表进行排序时,例如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/9f550094b3d24a35aebdUPD:在这里选择获胜者是一个艰难的选择,因为许多人都给出了很好的答案。@VincentvanderWeele,@大卫Eisenstat,@Coady,@ enrico.bacis和@srgerg提供完美产生最佳的置换函数。@tobias_k和David也回答了奖金问题(生成所有排列)。大卫还提供了正确性证明。@VincentvanderWeele的代码似乎是最快的。
查看完整描述

3 回答

?
慕哥9229398

TA贡献1877条经验 获得超6个赞

伪代码:


排序清单

循环遍历排序列表的前半部分,并填充结果列表的所有偶数索引

循环遍历排序列表的后半部分,并填充结果列表的所有奇数索引

仅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


查看完整回答
反对 回复 2019-12-21
?
守着星空守着你

TA贡献1799条经验 获得超8个赞

已经给出的算法将剩下的不是前一项的最常见项取走是正确的。这是一个简单的实现,可以最佳地使用堆来跟踪最常见的堆。


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]


查看完整回答
反对 回复 2019-12-21
  • 3 回答
  • 0 关注
  • 594 浏览
慕课专栏
更多

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信