Creating groups from a set without repeating past groups

Question

I'm trying to create a program that generates groups of students from a class but does not create groups that have been created before. Specifically, I need to create new student lab groups of 2 every week from the same set of students and I'm trying not to pair the same two students together more than once. The students which were paired in previous weeks will be given as an input somehow.

The past groups need to have their mirror images excluded as well, ie if [1,2] is a past group, [2,1] is also a past group.

My program is below. It solves the problem, but I guess it's highly inefficient. I'll accept completely different code if it's a better solution.

import numpy,random
from itertools import combinations
class_list="""a\nb\nc\nd\ne\nf\ng\nh\ni\nj\nk\nl\nm\nn\no\np
"""
students=class_list.splitlines()
#print len(students),students
combs=[map(int, comb) for comb in combinations(range(len(students)), 2)]
#print combs
done_list=[[0,4],[1,6],[2,13],[3,12],[8,10],[11,14],[15,9],
           [0,13],[1,4],[2,7],[3,12],[5,6],[8,10],[14,15],
           [0,1],[2,3],[4,5],[6,7],[8,9],[10,11],[12,15],[13,14],
           [0,2],[1,3],[4,6],[5,7],[8,14],[10,9],[12,11],[15,13]]
for i_done in done_list:
    if i_done in combs:
        combs.remove(i_done)
f_done=False
while(1):
    if f_done:
        break
    final_list=[]
    final_list_used_students=[]
    for _i in range(len(students)/2):
        rand_i=random.randint(0,len(combs)-1)
        if combs[rand_i][0] not in final_list_used_students and combs[rand_i][1] not in final_list_used_students:
            final_list.append(combs[rand_i])
            final_list_used_students.append(combs[rand_i][0])
            final_list_used_students.append(combs[rand_i][1])
        if len(final_list_used_students)==len(students):
            f_done=True
            break
print final_list

Answer 1

So basically you want to cover all items each time, where each item is selected only once and the order isn't important. SO I took a whole new different approach from before:

import itertools


def find_path(optional_pairs, num_pairs, result, used_population):
    if num_pairs == 0:
        return result

    while optional_pairs:
        _pair = optional_pairs.pop(0)
        if _pair[0] in used_population or _pair[1] in used_population:
            continue

        # Try omitting this _pair
        pairs = list(optional_pairs)
        result2 = find_path(pairs, num_pairs, list(result), list(used_population))
        if result2:
            return result2

        # Try adding pair to path
        used_pop = list(used_population)
        used_pop.append(_pair[0])
        used_pop.append(_pair[1])
        result2 = list(result)
        result2.append(_pair)

        pairs = list(optional_pairs)
        return find_path(pairs, num_pairs - 1, result2, used_pop)

    return []


def get_duos(population, excluded_duos):
    excluded_duos = excluded_duos + [(x[1], x[0]) for x in excluded_duos]
    all_combinations = itertools.permutations(population, 2)

    optional_pairs = set(all_combinations) - set(excluded_duos)

    return find_path(list(optional_pairs), len(population) / 2, [], [])


print get_duos(['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'], [('a', 'c'), ('b', 'g'), ('f', 'd'), ('e', 'h'), ('b', 'f'), ('g', 'c'), ('a', 'e'), ('h', 'd')])

I used the itertools.permutations that was mentioned in another answer, removed the excluded (and their mirrors) from the list and worked on that. Now the only trick is to make sure we do not select a pair that can create a no solution - as the remanding pairs cannot connect with it while covering all items. Therefore I use recursion and every step I try getting a solution with the pair and without until we find the solution.

Enjoy

Answer 2

For N choose 2, I think I just heard your specification boil down to:

itertools.combinations(students, r=2)

Docs are at https://docs.python.org/3/library/itertools.html#itertools.permutations

Feel free to randomly permute the whole list before running it through that.

Simply maintain a set describing previous lab assignments, and test a combination's membership in that set to reject repeat proposals.

EDIT: thank you, Antti Haapala, for the combinations remark

how do I search through this new set (that does not contain the discounted groups) and create a set ...

I think I don't quite understand the question. Assume that history is a set with historic student pairs, where a pair always appears in sorted order. Then it's just a matter of interrogating the generator and filtering, yes?

shuffled_students = [students[i]
                     for i in numpy.random.permutation(len(students))]
for pair in itertools.combinations(shuffled_students, r=2):
    pair = sorted(pair)
    if pair in history:
        continue
    history.add(pair)
    schedule_this(pair)

Answer 3

If you don't need to return the group randomly, then you may just remember the last group returned and keep "incrementing" the next group. Below sample code shows how you may do that for 50 students:

student_count = 50
students_nos = range(0, student_count)
current_group = (0, 1)
group_exhausted = False

def get_next_group():
    global current_group
    global group_exhausted
    if group_exhausted:
        return None
    ret = current_group
    if (current_group[0] == students_nos[student_count - 2]) and (current_group[1] == students_nos[student_count - 1]):
        group_exhausted = True
    if current_group[1] == students_nos[student_count - 1]:
        current_group = (current_group[0] + 1, current_group[0] + 2)
    else:
        current_group = (current_group[0], current_group[1] + 1)
    return ret

# Exmpale run.....
while True:
    cur = get_next_group()
    if cur is None:
        break
    print cur

Answer 4

First, we need to convert the already existing groups into a set of tuples. Each need to be additionally sorted because that's the order that itertools.combinations would produce them. Thus.

done_list=[[0,4],[1,6],[2,13],[3,12],[8,10],[11,14],[15,9], #first old set
           [0,13],[1,4],[2,7],[3,12],[5,6],[8,10],[14,15],#2nd old set
           [0,1],[2,3],[4,5],[6,7],[8,9],[10,11],[12,15],[13,14],#3rd old set
           [0,2],[1,3],[4,6],[5,7],[8,14],[10,9],[12,11],[15,13]]#4th old set

done_set = {tuple(sorted(i)) for i in done_list}

Then we can make a generator function that yields only elements that are not members of done_set:

from itertools import combinations

def unseen_combinations(items, n):
    for i in combinations(items, n):
        if i not in done_set:
            done_set.add(i)
            yield i


for combination in unseen_combinations(students, 2):
    print(combination)