重新排序列表以符合条件 [英] Reordering a list to meet conditions

问题描述

对于一所大学的某门课程，要求学生每周上课主题演讲.学生每周随机出现.

For a certain course at a university, students are expected to present on topics each week for class. The students present in a random order each week.

函数presOrder应该接收两个参数，(1)一个正整数n表示演示文稿的星期数，以及(2)名称列表，该列表仅在第一次演示文稿时必须保留.该函数返回一周的展示顺序的列表清单.每个列表以完全随机的顺序包含给定名称，以确保名称与前一周的顺序不同，并且每个名称与前一周的位置不同.顺序不同意味着上周之前和之后的名称在下周应该不同.

The function presOrder is supposed to receive two parameters, (1) a positive integer n representing a number of weeks of presentations, and (2) a list of names in the order that must be maintained only for the first presentation. The function returns a list of lists for the presentation order for the weeks; each of the lists contains the given names in a completely randomized order ensuring that the names are in a different order from that of the previous week and each name in a different position from that of the previous week. A different order means that the names before and after in the previous week should not be the same in the week following.

import random
import itertools

def notRandom(lst, plst, no):
    result = True
    for i in range(no-1):
        result = result and (lst[i] == plst[i+1])
    result = result and (lst[no-1] == plst[0])
    if result:
        return True
    result = True
    for i in range(1,no):
        result = result and (lst[i] == plst[i-1])
    result = result and (lst[0] == plst[no-1])
    if result:
        return True
    return False


# My attempt
def presOrder(n, namelst):
    permutation = itertools.permutations(namelst)
    rand = [] + [namelst]
    prev = namelst
    for lst in permutation:
        if not(notRandom(lst, prev, len(namelst))) and len(rand) < n:
            rndom = True
            for i in range(len(namelst)):
                if not(lst[i] == prev[i]):
                    rndom = rndom and True
                else:
                    rndom = rndom and False
            if rndom:
                rand += [lst]
                prev = lst[:]
        else:
            continue
    return rand


names = ['Abi Jones', 'Bob King', 'Carl Llewellyn', 'Danielle McIntosh', 'Earl Newell', 'Frank Olephante', 'George Brown', 'Harry Zephers']

#example
>>> print(presOrder(5, names))
>>> [['Abi Jones', 'Bob King', 'Carl Llewellyn', 'Danielle McIntosh', 'Earl Newell', 'Frank Olephante', 'George Brown', 'Harry Zephers'], ('Bob King', 'Abi Jones', 'Danielle McIntosh', 'Carl Llewellyn', 'Frank Olephante', 'Earl Newell', 'Harry Zephers', 'George Brown'), ('Carl Llewellyn', 'Bob King', 'Abi Jones', 'Danielle McIntosh', 'Earl Newell', 'Frank Olephante', 'George Brown', 'Harry Zephers'), ('Danielle McIntosh', 'Abi Jones', 'Bob King', 'Carl Llewellyn', 'Frank Olephante', 'Earl Newell', 'Harry Zephers', 'George Brown'), ('Earl Newell', 'Bob King', 'Abi Jones', 'Danielle McIntosh', 'Carl Llewellyn', 'Frank Olephante', 'George Brown', 'Harry Zephers')]

代码似乎可以(某种程度上)正常工作，但是我需要对其进行更多测试.同时，如何优化presOrder的代码?

The code seems to work (somewhat) as it is, but I'll need to test it more. In the meantime, how can I optimize the code for presOrder?

推荐答案

我的方法如下:

import random

def test_positions(L1, L2):
    return any(a==b for a, b in zip(L1, L2))

def neighbours(L):
    return [set([a, b]) for a, b in zip(L[:-1], L[1:])]

def test_neighbours(L1, L2):
    return any(nb in neighbours(L2) for nb in neighbours(L1))

def pres_order(n, L):
    result = [names[:]]
#   random.shuffle(result[0])    # only needed for reording first row
    for i in range(1, n):
        result.append(names[:])
        random.shuffle(result[-1])
        while test_positions(result[-1], result[-2]) or test_neighbours(result[-1], result[-2]):
            random.shuffle(result[-1])
    return result

想法是首先创建名称列表的(随机重新排序(随机))版本.
然后添加下一个经过改组的版本-但要反复进行改组，直到满足您的两个要求为止.
直到列表的长度== n.

The idea is to first create a (randomly reordered (shuffled)) version of the names list.
Then append a next shuffled version - but shuffle again and again until your two requirements are met.
Append until length of list == n.

这两个要求在test_...函数中实现.
我认为关于职位的第一个是自我解释.
第二个检查是否最后一行的任何邻居在最后一行(但只有一行)中也显示为邻居.
为此，有一个帮助程序功能可创建邻居对的列表.

The two requirements are implemented in the test_... functions.
The first one about positions is self explaining I think.
The second one checks if any neighbours of the last row appear also as neighbours in the last but one row.
To achieve this, there is a helper function to create the lists of neighbour pairs.

请注意，相邻定义中的set函数将防止相邻行中的相邻名称对独立于其顺序.如果您只想阻止一对的精确复制(例如，应允许在[...'E', 'G',... ] [...'G', 'E',... ]之后但不允许在[...'E', 'G',... ]之后)，则可以简单地将set函数保留.

Note that the set function in the neighbour definition will prevent neighboured name pairs in adjacent rows independant of their order. If you want to prevent only the exact copy of a pair (e.g. after [...'E', 'G',... ] [...'G', 'E',... ] should be allowed but [...'E', 'G',... ] not), you can simply leave the set function away.

示例:

names = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']
for l in pres_order(5, names):
    print(l)

# ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']
# ['G', 'B', 'H', 'E', 'C', 'F', 'A', 'D']
# ['H', 'C', 'B', 'A', 'E', 'D', 'F', 'G']
# ['C', 'F', 'E', 'H', 'A', 'G', 'B', 'D']
# ['G', 'H', 'B', 'F', 'D', 'A', 'E', 'C']

---

我只是意识到第一行应该是未更改的原始列表.因此，我评论了第一次洗牌；因此您可以根据需要轻松地将其取回.

---

I just realized that the first row should be the unaltered original list. Therefore I commented the first shuffle out; so you can easily get it back if you need to.

这篇关于重新排序列表以符合条件的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！