Random subset generator

Question

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.

Answer 1

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

Try it online here.

Answer 2

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}