# Random subset generator [closed]

Randomly choose one out of k-length, ordered subset of characters in a string, while only storing a limited number of characters. The subset must be chosen with equal probability and may contain repeated characters. Do this without generating all possible permutations and assume k is at most the length of the string. For example, the string daddy has 7 subsets of length two: da, dd, dy, ad, ay, yd, ya. The function should return any one of them with the probability of 1/7.

• You probably don't mean substring. te isn't a substring for example. – Maltysen Mar 11 '17 at 20:03
• It would be nice to have a bit of a stronger specification. An example is not really a satisfactory specification. – Post Rock Garf Hunter Mar 11 '17 at 20:03
• The usual term for non-contiguous substrings is "subsequence". But since you also seem to allow arbitrary orders, you probably want "subsets" or "sub-multisets", since you've included ee. – Martin Ender Mar 11 '17 at 20:06
• updated to subsets – ash Mar 13 '17 at 1:46
• I think this question is asking, "choose 1 out of a set of k-lengthed, ordered subsets of the characters in a word, where the same character is equivalent (e.g. 'te' with the first e = 'te' with the second), with equal prabability" – MildlyMilquetoast Mar 13 '17 at 1:50

# Pyth - 5 bytes

While we're arguing about the nomenclature, I'm just guessing at the rules based on the example to just mean pick one from all unique permutations of length n of the string.

O{.PF

• permutation works, but what if k is large? – ash Mar 13 '17 at 3:39
• @ash then it's really slow – Maltysen Mar 13 '17 at 3:46

# Perl 6,  75  71 bytes

{set(flat $^a.comb.combinations($^b).map: *.permutations.map: *.join).pick}


Try it

{set($^a.comb.combinations($^b).map: |*.permutations.map: *.join).pick}


Try it

## Expanded:

{
set(                         # get the unique values from: (equal probability)

$^a.comb.combinations($^b) # get the combinations
.map: |*.permutations    # get the permutations of the combinations
.map: *.join           # join each permutation into a string

).pick                       # pick one
}


The following could almost work except that it has a different probability if there are any repeats of characters.

{$^a.comb.pick($^b).join}