2
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ You probably don't mean substring. te isn't a substring for example. \$\endgroup\$ – Maltysen Mar 11 '17 at 20:03
  • 1
    \$\begingroup\$ It would be nice to have a bit of a stronger specification. An example is not really a satisfactory specification. \$\endgroup\$ – Post Rock Garf Hunter Mar 11 '17 at 20:03
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ – Martin Ender Mar 11 '17 at 20:06
  • \$\begingroup\$ updated to subsets \$\endgroup\$ – ash Mar 13 '17 at 1:46
  • 1
    \$\begingroup\$ 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" \$\endgroup\$ – MildlyMilquetoast Mar 13 '17 at 1:50
1
\$\begingroup\$

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.

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

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}
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.