如何在python中对列表进行排序，使具有相同类的两个值不会成为邻居？

Question

我有一个python类列表，例如list1 = [1, 1, 0, 1, 0, 0, 1, 1]。我想像这样对一个列表进行排序list 2 = list(range(len(list1))) = [0, 1, 2, 3, 4, 5, 6, 7]，这样同一类的两个值就不会彼此靠近。对于我的例子，结果是[0, 2, 1, 4, 3, 5, 6]。第七个会被忽略，因为我需要尽可能地坚持原来的清单。这个任务有什么排序算法吗？如何有效实施？你知道吗

详细说明我是如何得到最终名单的：

1）将列表2中的值0放入最终结果列表：res = [0,]。它有类1（列表1[0]）


2）检查list2（“1”）类中的下一个值。在这个例子中，它也是1，所以我们不把它们放在一起然后继续

3）检查list2（“2”）类中的下一个值。它是类0，它不等于previus value的类，所以我们可以将它附加到result:res = [0, 2,]

4）现在我回到前面跳过的值（“1”）并将其添加到最终列表中。res=[0, 2, 1,]。他们现在的课程是[1，0，1]。你知道吗


5）我们继续从列表2中选择值“3”。它有类1，所以我们不能将它添加到列表中


6）从列表2中转到值“4”。它的类是0，所以我们可以添加它：res = [0, 2, 1, 4,]。这些值的类类似于[1，0，1，0]


7）返回值“3”，检查是否可以立即添加。结果列表中的最后一个类是0，“3”有类1，所以我们可以添加它。res = [0, 2, 1, 4, 3,]，它们的类=[1，0，1，0，1]


8）从列表2中移到值“5”。它有类0，将它添加到结果res = [0, 2, 1, 4, 3, 5,]，它们的类=[1，0，1，0，1，0]


9）从列表2中转到值“6”。它有类1，所以我把它添加到最后一个列表：res = [0, 2, 1, 4, 3, 5, 6]，它们的类=[1，0，1，0，1]

10）现在我必须检查列表2中的最后一个值-“7”。我无法将其添加到list6中，因为这样我的类将如下所示：[1，0，1，0，1，1]，我不希望发生这种情况，所以我只从最终结果中省略值“7”。你知道吗

我不明白如何编写这个代码，特别是在我有两个以上类的情况下。你知道吗

Answer 1

一个简单的解决方案是将每个类型“隔离”到它们自己的列表中，然后在附加时在它们之间交替：

list1 = [1, 1, 0, 1, 0, 0, 1, 1]
sorted_list = []
sorted_list_indices = []

# Isolate each type to their own list of (index, item)
types = {
    'type0': [(ind, x) for ind, x in enumerate(list1) if x == 0],
    'type1': [(ind, x) for ind, x in enumerate(list1) if x == 1]
    }


# Alternate between the lists of each type, starting with the bigger list
alternator = 'type0' if len(types['type0']) > len(types['type1']) else 'type1'

for i in range(0, len(list1)):
    # Break if one of the lists is empty
    if len(types[alternator]) == 0: break
    # Pop the first item from the "current" list and append it to the output
    tup = types[alternator].pop(0)
    sorted_list_indices.append(tup[0])
    sorted_list.append(tup[1])
    # Switch to the other type
    alternator = 'type0' if alternator == 'type1' else 'type1'

print sorted_list
# [1, 0, 1, 0, 1, 0, 1]
print sorted_list_indices
# [0, 2, 1, 4, 3, 5, 6]

更新：下面是另一个利用zip内置函数的示例：

list1 = [1, 1, 0, 1, 0, 0, 1, 1]
sorted_list = []
sorted_list_indices = []

# Isolate each type to their own list of (index, item)
type0 = [(ind, x) for ind, x in enumerate(list1) if x == 0]
# [(2, 0), (4, 0), (5, 0)]
type1 = [(ind, x) for ind, x in enumerate(list1) if x == 1]
# [(0, 1), (1, 1), (3, 1), (6, 1), (7, 1)]

big_list = type0 if len(type0) > len(type1) else type1
small_list = type0 if len(type0) <= len(type1) else type1

# Shrink the big list to make it larger by one at most
big_list = big_list[:len(small_list)+1]

# Use zip to get a list of tuples as (big_list, small_list)
zipped_list = zip(big_list, small_list)
# [((0, 1), (2, 0)), ((1, 1), (4, 0)), ((3, 1), (5, 0))]

# If big_list is indeed larger, we append its last item to our zipped_list
if len(big_list) > len(small_list): zipped_list.append((big_list[-1],))
# [((0, 1), (2, 0)), ((1, 1), (4, 0)), ((3, 1), (5, 0)), ((6, 1),)]

# Flatten the zipped list of tuples
sorted_list = [tup[1] for zipped in zipped_list for tup in zipped]
sorted_list_indices = [tup[0] for zipped in zipped_list for tup in zipped]

print sorted_list
# [1, 0, 1, 0, 1, 0, 1]
print sorted_list_indices
# [0, 2, 1, 4, 3, 5, 6]