Create many constrained, random permutation of a list
-
01-07-2019 - |
Question
I need to make a random list of permutations. The elements can be anything but assume that they are the integers 0 through x-1. I want to make y lists, each containing z elements. The rules are that no list may contain the same element twice and that over all the lists, the number of times each elements is used is the same (or as close as possible). For instance, if my elements are 0,1,2,3, y is 6, and z is 2, then one possible solution is:
0,3 1,2 3,0 2,1 0,1 2,3
Each row has only unique elements and no element has been used more than 3 times. If y were 7, then 2 elements would be used 4 times, the rest 3.
Solution
This could be improved, but it seems to do the job (Python):
import math, random
def get_pool(items, y, z):
slots = y*z
use_each_times = slots/len(items)
exceptions = slots - use_each_times*len(items)
if (use_each_times > y or
exceptions > 0 and use_each_times+1 > y):
raise Exception("Impossible.")
pool = {}
for n in items:
pool[n] = use_each_times
for n in random.sample(items, exceptions):
pool[n] += 1
return pool
def rebalance(ret, pool, z):
max_item = None
max_times = None
for item, times in pool.items():
if times > max_times:
max_item = item
max_times = times
next, times = max_item, max_times
candidates = []
for i in range(len(ret)):
item = ret[i]
if next not in item:
candidates.append( (item, i) )
swap, swap_index = random.choice(candidates)
swapi = []
for i in range(len(swap)):
if swap[i] not in pool:
swapi.append( (swap[i], i) )
which, i = random.choice(swapi)
pool[next] -= 1
pool[swap[i]] = 1
swap[i] = next
ret[swap_index] = swap
def plist(items, y, z):
pool = get_pool(items, y, z)
ret = []
while len(pool.keys()) > 0:
while len(pool.keys()) < z:
rebalance(ret, pool, z)
selections = random.sample(pool.keys(), z)
for i in selections:
pool[i] -= 1
if pool[i] == 0:
del pool[i]
ret.append( selections )
return ret
print plist([0,1,2,3], 6, 2)
OTHER TIPS
Ok, one way to approximate that:
1 - shuffle your list
2 - take the y first elements to form the next row
4 - repeat (2) as long as you have numbers in the list
5 - if you don't have enough numbers to finish the list, reshuffle the original list and take the missing elements, making sure you don't retake numbers.
6 - Start over at step (2) as long as you need rows
I think this should be as random as you can make it and will for sure follow your criteria. Plus, you have very little tests for duplicate elements.
First, you can always randomly sort the list in the end, so let's not worry about making "random permutations" (hard); and just worry about 1) making permutations (easy) and 2) randomizing them (easy).
If you want "truly" random groups, you have to accept that randomization by nature doesn't really allow for the constraint of "even distribution" of results -- you may get that or you may get a run of similar-looking ones. If you really want even distribution, first make the sets evenly distributed, and then randomize them as a group.
Do you have to use each element in the set x evenly? It's not clear from the rules that I couldn't just make the following interpretation:
Note the following: "over all the lists, the number of times each elements is used is the same (or as close as possible)"
Based on this criteria, and the rule that z < x*, I postulate that you can simply enumerate all the items over all the lists. So you automatically make y list of the items enumerated to position z. Your example doesn't fulfill the rule above as closely as my version will. Using your example of x={0,1,2,3} y=6 and z=2, I get: 0,1 0,1 0,1 0,1 0,1 0,1
Now I didn't use 2 or 3, but you didn't say I had to use them all. If I had to use them all and I don't care to be able to prove that I am "as close as possible" to even usage, I would just enumerate across all the items through the lists, like this: 0,1 2,3 0,1 2,3 0,1 2,3
Finally, suppose I really do have to use all the elements. To calculate how many times each element can repeat, I just take (y*z)/(count of x). That way, I don't have to sit and worry about how to divide up the items in the list. If there is a remainder, or the result is less than 1, then I know that I will not get an exact number of repeats, so in those cases, it doesn't much matter to try to waste computational energy to make it perfect. I contend that the fastest result is still to just enumerate as above, and use the calculation here to show why either a perfect result was or wasn't achieved. A fancy algorithm to extract from this calculation how many positions will be duplicates could be achieved, but "it's too long to fit here in the margin".
*Each list has the same z number of elements, so it will be impossible to make lists where z is greater than x and still fulfill the rule that no list may contain the same element twice. Therefore, this rule demands that z cannot be greater than x.
Based on new details in the comments, the solution may simply be an implementation of a standard random permutation generation algorithm. There is a lengthy discussion of random permutation generation algorithms here:
http://www.techuser.net/randpermgen.html
(From Google search: random permutation generation)
This works in Ruby:
# list is the elements to be permuted
# y is the number of results desired
# z is the number of elements per result
# equalizer keeps track of who got used how many times
def constrained_permutations list, y, z
list.uniq! # Never trust the user. We want no repetitions.
equalizer = {}
list.each { |element| equalizer[element] = 0 }
results = []
# Do this until we get as many results as desired
while results.size < y
pool = []
puts pool
least_used = equalizer.each_value.min
# Find how used the least used element was
while pool.size < z
# Do this until we have enough elements in this resultset
element = nil
while element.nil?
# If we run out of "least used elements", then we need to increment
# our definition of "least used" by 1 and keep going.
element = list.shuffle.find do |x|
!pool.include?(x) && equalizer[x] == least_used
end
least_used += 1 if element.nil?
end
equalizer[element] += 1
# This element has now been used one more time.
pool << element
end
results << pool
end
return results
end
Sample usage:
constrained_permutations [0,1,2,3,4,5,6], 6, 2
=> [[4, 0], [1, 3], [2, 5], [6, 0], [2, 5], [3, 6]]
constrained_permutations [0,1,2,3,4,5,6], 6, 2
=> [[4, 5], [6, 3], [0, 2], [1, 6], [5, 4], [3, 0]]
enter code here