How to shuffle a fixed sum array of rows / columns?
I need to assign random documents to class students, but I have limitations that:
- Each student must have two articles assigned.
- Each document must be assigned (approximately) the same number of students.
Is there an elegant way to create a matrix that has this property? those. is shuffled but the row and column sums are constant? By way of illustration:
Student A 1 0 0 1 1 0 | 3
Student B 1 0 1 0 0 1 | 3
Student C 0 1 1 0 1 0 | 3
Student D 0 1 0 1 0 1 | 3
----------------
2 2 2 2 2 2
I was thinking about first creating an "original matrix" with the correct row / column sum, then randomly rearranging rows first, then columns , but how can I create this initial matrix ? The problem here is that I would choose between (for example) the following alternatives, and the fact that there are two students with the same pair of documents assigned (in the left setting) will not change when the rows / columns are shuffled:
INITIAL (MA): OR (MB):
A 1 1 1 0 0 0 || 1 1 1 0 0 0
B 1 1 1 0 0 0 || 0 1 1 1 0 0
C 0 0 0 1 1 1 || 0 0 0 1 1 1
D 0 0 0 1 1 1 || 1 0 0 0 1 1
I know I can come up with something quick / dirty and just tweak where needed, but it felt like a fun exercise.
source to share
If you want to do permutations, how about:
-
Pick a student at random, say student 1
-
For this student, pick a random paper he has, say paper A
-
Randomly select another student
-
For this student, pick a random paper he has, say paper B (other than A)
-
Give paper B to student 1 and paper A to student 2.
This way, you keep both the number of different documents and the number of documents for each student. Indeed, both students give one document and receive it back. Moreover, no paper is created or deleted.
In terms of the table, this means searching for two pairs of indices (i1, i2) and (j1, j2) such that A (i1, j1) = 1, A (i2, j2) = 1, A (i1, j2) = 0, and A (i2, j1) = 0 and changing 0s for 1s and 1s for 0s => The sums of rows and columns are not changed.
Note 1: If you don't want to continue rearranging, you can simply put all the paper in the vector (put paper A 2 times, B paper 2 times, ...). Then an arbitrary random shuffle of the vector and attribute k first to the first student and the next to student 2, ... However, you can end up with a student having the same paper multiple times. In this case, make several rearrangements, starting with the popular paper.
source to share
You can create the original matrix like this (pseudo python syntax):
column_sum = [0] * n_students
for i in range(n_students):
if column_sum[i] < max_allowed:
for j in range(i + 1, n_students):
if column_sum[j] < max_allowed:
generate_row_with_ones_at(i, j)
column_sum[i] += 1
column_sum[j] += 1
if n_rows == n_wanted:
return
This simple iteration over the whole n selects 2 different rows, but with a constraint on the column sums to be done as early as possible.
source to share