如何在Python中重新排列列表以避免重复元素？

我试图检查一个列表是否有任何连续的重复元素，然后重新排序，以避免重复。如果那是不可能的，那么返回False。例如：如何在Python中重新排列列表以避免重复元素？

checkRepeat([1,2]) 
Out[61]: [1, 2] 

checkRepeat([1,2,2]) 
Out[62]: [2, 1, 2] 

checkRepeat([1,2,2,1,1]) 
Out[63]: [1, 2, 1, 2, 1] 

checkRepeat([1,2,2,1,1,3,3,3,3]) 
Out[64]: [1, 3, 1, 3, 2, 1, 3, 2, 3] 

checkRepeat([1,2,2,1,1,3,3,3,3,3]) 
Out[65]: [3, 1, 3, 2, 3, 1, 3, 1, 3, 2] 

checkRepeat([1,2,2,1,1,3,3,3,3,3,3]) 
Out[66]: [3, 1, 3, 1, 3, 1, 3, 2, 3, 2, 3] 

checkRepeat([1,2,2,1,1,3,3,3,3,3,3,3]) 
Out[67]: False

这是我的。有没有更优雅的解决方案？

from itertools import groupby 
def checkRepeat(lst,maxIter=1000): 
    """Returns a list that has no repeating elements. Will try for a max of 1000 iterations by default and return False if such a list can't be found""" 

    def hasRepeat(lst): 
     """Returns true if there are any repeats""" 
     return len([x[0] for x in groupby(lst)]) < len(lst) 


    offset=numIter=0   
    while hasRepeat(lst) and numIter<maxIter: 
     for i,curElt in enumerate(lst): 
      try: 
       if lst[i]==lst[i+1]: 
        lst[i+1],lst[(i+offset) % len(lst)] = lst[(i+offset) % len(lst)],lst[i+1] #swap j+1 with j+offset. wrap around the list 
      except: 
       break 
     offset+=1 
     numIter+=1 
    if numIter==maxIter: 
     return False 
    else: 
     return lst

来源

2015-10-15 glupyan

如果您有需要改进的工作代码，它可能非常适合[代码评论]（http://codereview.stackexchange.com/）。 – TigerhawkT3

只是头脑风暴的算法，但我可能会通过建立每个元素的计数，然后添加具有最高未使用计数的非上一个元素的实例。如果在任何时候您的所有非先前元素都有0个可用计数，则返回false。它只需要对原始列表进行两次遍历，一次对元素进行计数，然后一次对重新排序的列表中的每个元素进行选择。 –

@Heslacher - 从“是否有更优雅的解决方案”，我认为OP有某种工作解决方案，并希望尽可能使其更优雅。 – TigerhawkT3

您可以尝试概率公式，其重复的次数最多，必须始终lessthen其他号码的数量

号码。

[1,2,2,1,1,3,3,3,3,3,3,3] 
7< (3+2) false 

[1,2,2,1,1,3,3,3,3,3,3] 
6< (3+2) true 

[1,2,2,1,1,3,3,3,3,3] 
5< (3+3) true

代码

from itertools import groupby 
>>> a =[1,2,2,1,1,3,3,3,3,3] 
>>> s = [len(list(group)) for key, group in groupby(a)] 
>>> s 
[1, 2, 2, 5] 
>>> max(s) < (sum(s)-max(s)) 
True

来源

2015-10-15 06:30:27 Ravichandra

这是我提到在评论中实现，使用非常有用collections.Counter类算法：

from collections import Counter 

def check_repeat(sequence): 
    if not sequence: 
     return [] 
    element_counts = Counter(sequence) 
    new_sequence = [] 
    elements_chosen = 0 
    elements_needed = len(sequence) 
    previous_element_chosen = None 
    while elements_chosen < elements_needed: 
     candidates_needed = 1 if previous_element_chosen is None else 2 
     candidates = element_counts.most_common(candidates_needed) 
     candidate = (candidates[0] if 
      (len(candidates) < 2 or candidates[0][0] != previous_element_chosen) 
      else candidates[1]) 
     if candidate[1] <= 0: 
      return False 
     else: 
      new_sequence.append(candidate[0]) 
      element_counts[candidate[0]] -= 1 
      previous_element_chosen = candidate[0] 
      elements_chosen += 1 
    return new_sequence

这需要一些细化，如果None是一个有效值你的顺序，或者你是否在乎任何程度的稳定性。如果序列中的元素不可散列，那么它根本无法工作。

而那三元candidate = ...作业可能更清晰分解多一点。

来源

2015-10-15 06:33:25

如何在Python中重新排列列表以避免重复元素？

回答

相关问题