Return to Question

I have string \$s\$ of length \$n\$ and some constant integer \$k\$ which is at most \$n\$. Give the fastest algorithm to sample a random string with Levenshtein distance \$k\$ from \$s\$ uniformly.

Your algorithm should output any of the strings with edit distance exactly \$k \leq n\$ from the input string \$s\$ with the same probability. You should assume that only the characters in the string \$s\$ are used.

For example, if \$s\$ = "1111011010" the number of strings with distance \$k\$ is

 k | # of results

 0              1
 1             28
 2            302
 3           1652
 4           5533
 5          14533
 6          34808
 7          80407
 8         180663
 9         395923

If \$k\$ = 9 you should output of the 395923 possible output strings chosen uniformly at random.

I have string \$s\$ of length \$n\$ and some constant integer \$k\$ which is at most \$n\$. Give the fastest algorithm to sample a random string with Levenshtein distance \$k\$ from \$s\$ uniformly.

Your algorithm should output any of the strings with edit distance exactly \$k \leq n\$ from the input string \$s\$ with the same probability. You should assume that only the characters in the string \$s\$ are used.

For example, if \$s\$ = "1111011010" the number of strings with distance \$k\$ is

 k | # of results

 0              1
 1             28
 2            302
 3           1652
 4           5533
 5          14533
 6          34808
 7          80407
 8         180663
 9         395923

If \$k\$ = 9 you should output one of the 395923 possible output strings chosen uniformly at random.

I have string s of length n and some constant integer k which is at most n. Give the fastest algorithm to sample a random string with Levenshtein distance k from s uniformly?

Your algorithm should output any of the strings with edit distance exactly \$k \leq n\$ from the input string s with the same probability. You should assume that only the characters in the string s are used.

For example, if s = "1111011010" the number of strings with distance k is

 k | # of results

 0              1
 1             28
 2            302
 3           1652
 4           5533
 5          14533
 6          34808
 7          80407
 8         180663
 9         395923

If k = 9 you should output of the 395923 possible output strings chosen uniformly at random.

I have string \$s\$ of length \$n\$ and some constant integer \$k\$ which is at most \$n\$. Give the fastest algorithm to sample a random string with Levenshtein distance \$k\$ from \$s\$ uniformly.

Your algorithm should output any of the strings with edit distance exactly \$k \leq n\$ from the input string \$s\$ with the same probability. You should assume that only the characters in the string \$s\$ are used.

For example, if \$s\$ = "1111011010" the number of strings with distance \$k\$ is

 k | # of results

 0              1
 1             28
 2            302
 3           1652
 4           5533
 5          14533
 6          34808
 7          80407
 8         180663
 9         395923

If \$k\$ = 9 you should output of the 395923 possible output strings chosen uniformly at random.

I have string s of length n and some constant integer k which is at most n. Give the fastest algorithm to sample a random string with edit (also known as Levenshtein) distance k from s uniformly?

Your algorithm should output any of the strings with edit distance exactly \$k \leq n\$ from the input string s with the same probability. You should assume that only the characters in the string s are used.

For example, if s = "1111011010" the number of strings with distance k is

 k | # of results

 0              1
 1             28
 2            302
 3           1652
 4           5533
 5          14533
 6          34808
 7          80407
 8         180663
 9         395923

If k = 9 you should output of the 395923 possible output strings chosen uniformly at random.

I have string s of length n and some constant integer k which is at most n. Give the fastest algorithm to sample a random string with Levenshtein distance k from s uniformly?

Your algorithm should output any of the strings with edit distance exactly \$k \leq n\$ from the input string s with the same probability. You should assume that only the characters in the string s are used.

For example, if s = "1111011010" the number of strings with distance k is

 k | # of results

 0              1
 1             28
 2            302
 3           1652
 4           5533
 5          14533
 6          34808
 7          80407
 8         180663
 9         395923

If k = 9 you should output of the 395923 possible output strings chosen uniformly at random.