cụ thể danh sách shuffling bằng Python

Question

Vì vậy, tôi có một danh sách của các nhóm

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

và tôi cần phải xáo trộn một phiên bản phẳng của danh sách này

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

để các phần tử của cùng một nhóm sẽ kết thúc ở khoảng cách nào đó với nhau. Ví dụ.

[a, c, b, d, f, e] và không [a, c, b, d, e, f], vì d và e thuộc cùng một nhóm.

Tôi không quan tâm nếu khoảng cách chỉ là một phần tử trở lên, nhưng bất kỳ thành phần nào phải không ở gần yếu tố khác từ nhóm đó. Có bất kỳ thuật toán cho điều này?

Thuật toán cũng cần phải biết nếu điều này không thể thực hiện được.

Answer 1

Mã này tạo bản sao các nhóm ban đầu của bạn và mất mỗi lần một phần tử ngẫu nhiên từ nhóm (còn lại tại mỗi thời điểm) lớn nhất còn lại. Không hoàn toàn ngẫu nhiên, nhưng nên làm việc cho mọi trường hợp khi không có nhóm với hơn một nửa của tất cả các yếu tố.

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 

Answer 2

Chỉ cần một nhanh, mã không-rất-nhã:

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 

Mặc dù vấn đề mà có thể xảy ra là trường hợp khi chỉ có một khối cho sự lựa chọn. Giống như trong trường hợp này:

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

Tất nhiên phải có một số loại bắt ngoại lệ này, nhưng bây giờ tôi hy vọng mã này có thể cung cấp cho bạn một số ý tưởng làm thế nào để giải quyết vấn đề của bạn.

• Được chỉnh sửa do một ngoại lệ xảy ra một lần trong một thời gian.
• Quên không sử dụng các từ như "danh sách" làm tên biến. Cảm ơn bạn đã nhận xét - không được chỉnh sửa

Answer 3

Hãy để tôi lấy một cách tiếp cận khác nhau từ các câu trả lời hiện tại

Nguyên tắc cơ bản sẽ được shuffle mỗi danh sách trong danh sách, sort nó dựa trên chiều dài, zip_longest dựa trên lập luận biến mà được truyền từ danh sách và cuối cùng là chain danh sách và sau đó unwrap nó.điều đặc biệt cần lưu ý ở đây như thế nào chúng ta có thể vượt qua một danh sách như một args biến để một iterator, mà làm cho cuộc sống dễ dàng hơn ở đây :-)

Cho phép nói danh sách của bạn là

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

Danh sách công việc của tôi (sau khi sao chép để giữ gìn danh sách ban đầu)

workList=yourList[::] 

Xáo trộn mỗi danh sách trong danh sách của bạn

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

Nex t chúng tôi sắp xếp danh sách dựa trên độ dài của mỗi danh sách

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

và sau đó cuối cùng chaining qua danh sách xáo trộn nén

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

Và danh sách cuối cùng của bạn trông như

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

Answer 4

Tôi sẽ cung cấp cho câu trả lời "câm", đơn giản: chỉ cần san bằng danh sách, sau đó lặp lại ngẫu nhiên cho đến khi bạn nhận được danh sách có thể chấp nhận được.

Phương pháp này có tài sản được phân phối thống nhất trong tất cả các danh sách pháp lý, cũng như dễ dàng chứng minh chính xác và dễ hiểu đối với mã. Đó là bất lợi duy nhất là nó có thể trở nên chậm - nhưng với trường hợp sử dụng được đề cập trong một bình luận khác, tôi tin rằng nó sẽ đủ nhanh.

Đối với "là có thể" - cho nó một cái nhìn đầu tiên, tôi nghĩ rằng nó sẽ có thể nếu và chỉ khi không có nhóm có hơn một nửa các yếu tố, làm tròn lên. Nếu bạn xem xét các phần tử đầu tiên và cuối cùng liền kề, thay đổi "làm tròn" thành "làm tròn xuống".