Конкретный список перетасовки в Python

Итак, у меня есть список групп

[['a', 'b'], ['c', 'd', 'e'], ['f']]

и мне нужно перетасовать сплющенную версию этого списка

[a, b, c, d, e, f]

чтобы элементы одной и той же группы заканчивались на некотором расстоянии друг от друга. E. g.

[a, c, b, d, f, e], а не [a, c, b, d, e, f], потому что d и e находятся в одной и той же группе.

Мне все равно, если расстояние - это всего лишь один элемент или больше, но любой элемент не должен находиться рядом с другим элементом из его группы. Есть ли какой-нибудь алгоритм для этого?

Алгоритм также должен сказать, не может ли это сделать.

Ответ 1

Этот код делает копию вашего исходного списка групп и каждый раз принимает случайный элемент из (в каждый момент) самой большой оставшейся группы. Не совсем рандомизирован, но должен работать в любом случае, когда нет группы с половиной всех элементов.

import random

list_of_groups = [['a', 'b'], ['c', 'd', 'e'], ['f']]
l = [group[:] for group in list_of_groups] # make a copy
random.shuffle(l)
out = []
prev_i = -1
while any(a for a in l):
    new_i = max(((i,a) for i,a in enumerate(l) if i != prev_i), key=lambda x: len(x[1]))[0]
    out.append(l[new_i].pop(random.randint(0, len(l[new_i]) - 1)))
    prev_i = new_i

print out

Ответ 2

Позвольте мне применить подход, отличный от текущих ответов

Основным принципом будет перетасовать каждый список в списке, sort он основан на длине zip_longest на основе переменных аргументов, которые передаются из списка и, наконец, chain и разверните его. Особо следует отметить, как мы можем передать список как переменную args для итератора, что облегчило жизнь здесь: -)

Допустим, что ваш список

yourList=[['a', 'b'],['c', 'd', 'e'],['f']]

Мой рабочий список (после копирования для сохранения исходного списка)

workList=yourList[::]

Перетасовка каждого списка из списка

[random.shuffle(x) for x in workList]

Далее мы сортируем список по длине каждого списка

workList.sort(key=len,reverse=True)

а затем, наконец, цепочка над зашифрованным перетасованным списком

[x for x in itertools.chain(*[x for x in itertools.izip_longest(*workList)]) if x]

И ваш итоговый список выглядит как

['e', 'b', 'f', 'c', 'a', 'd']

Ответ 3

Просто быстрый, не очень элегантный код:

example = [[1, 2], [3, 4, 5], [6]]
result = []
block = None
last_block = None

while example:
    if block:
        last_block = block

    block = choice(example)

    if last_block:
        example.append(last_block)

    element = choice(block)
    result.append(element)

    block.remove(element)
    example.remove(block)
    example = [a for a in example if a]

print result

Хотя проблема может произойти, это случай, когда есть только один блок для выбора. Как в этом случае:

[1, 6, 2, 3, 4, 5]

Конечно, должно быть какое-то перехват этого исключения, но пока я надеюсь, что этот код может дать вам некоторое представление о том, как решить вашу проблему.

Отредактировано из-за того, что время от времени происходит исключение.
Нельзя использовать слова типа "список" в качестве имени переменной. Спасибо за комментарий - не исправлено.

Ответ 4

Я собираюсь дать "немой", простой ответ: просто сгладьте список, затем неоднократно произвольно перетасуйте его, пока не получите приемлемый список.

Этот метод обладает свойством быть равномерно распределенным среди всех юридических списков, а также легко доказывать правильность и простоту кодирования. Недостатком является то, что он может оказаться медленным, но, учитывая случай использования, упомянутый в другом комментарии, я считаю, что он будет достаточно быстрым.

Что касается "возможно ли это" - давая ему первый взгляд, я думаю, что это должно быть возможно, если и только если ни одна группа не имеет более половины элементов, округленных вверх. Если вы считаете, что первый и последний элементы смежны, измените "округленное" на "округленное".