Report Session 5

Report Session 5#

Write functions in the following cells to:

list the (tuple-like) arrangements of k elements from a set S
draw an arrangement of k from a set S in a uniformly
list the combinations (of type Set) of k elements among a set S
draw a combination of k from a set S in a uniform way

You can use the algorithms of your choice and be inspired by those seen during the session (subsets, Cartesian product, binary trees).

Ecrivez dans les cellules suivantes des fonctions permettant de :

lister les arrangements (de type tuple) de k éléments parmi un ensemble S
tirer un arrangement de k parmi un ensemble S de façon uniforme
lister les combinaisons (de type Set) de k éléments parmi un ensemble S
tirer une combinaison de k parmi un ensemble S de façon uniforme

Vous pouvez utiliser les algorithmes de votre choix et vous inspirez de ceux vus pendant la séance (sous-ensembles, produit cartésien, arbres binaires).

EDIT THIS CELL

Arrangements:

Describe the algorithm you used for listing arragements (recursive, unrank function, other method…)

…

Describe the algorithm you used for random generation (recursive, unrank function, other method…). What is its complexity?

…

Combinations:

Describe the algorithm you used for listing combinations (recursive, unrank function, other method…)

…

Describe the algorithm you used for random generation (recursive, unrank function, other method…). What is its complexity?

…

# Write your code here

Some examples to test your code (to be adapted / completed according to your code)

Quelques exemples pour tester votre code (à adapter / compléter en fonction de votre code)

Hand = Set(["Red","Blue","Green","Yellow"])
list(arrangements(Hand,2)) # arrangements is the function you need to write

# check that this is the same as in Sage
assert set(arrangements(Hand,2)) == set(tuple(a) for a in Arrangements(Hand,2)) 

assert all(set(arrangements(Hand,i)) == set(tuple(a) for a in Arrangements(Hand,i)) for i in range(5))

random_arrangement(Hand,2) # random_arrangement is the function you need to write

def distribution(L):
    """
    Return the distribution by number of occurrences of a list of elements
    Input:
     - a list L of (non-mutable) elements
    Output: a dictionary counting the occurrences of each element of the list L
    """
    d = {}
    for el in L:
        d[el] = d.get(el, 0) + 1
    return d

# check that the distribution is uniform
distribution([random_arrangement(Hand,2) for i in range(10000)])

bar_chart(list(distribution([random_arrangement(Hand,2) for i in range(10000)]).values()), ymin = 0)

# Now let's test the random generation on something bigger
S = Set(range(1000))

a = random_arrangement(S,10) # this should be very fast
a

# still very fast
b = random_arrangement(S,500)
c = random_arrangement(S,1000)

list(combinations(Hand,2)) # combinations is the the function you need to write

# check that this is the same as in Sage
assert set(combinations(Hand,2)) == set(Set(c) for c in Combinations(Hand,2))

assert all(set(combinations(Hand,i)) == set(Set(a) for a in Combinations(Hand,i)) for i in range(5))

random_combination(Hand,2) # random_combination is the function you need to write

# check that the distribution is uniform
distribution([random_combination(Hand,2) for i in range(10000)])

bar_chart(list(distribution([random_combination(Hand,2) for i in range(10000)]).values()), ymin = 0)

# Now let's test the random generation on something bigger
S = Set(range(1000))

a = random_combination(S,10) # this should be very fast
a

# still very fast
b = random_combination(S,500)
c = random_combination(S,1000)