3 ms·

I played around with this one I found on Reddit's "daily programmer" subreddit a few months back, never found a great approach other than brute force (along wit

I played around with this one I found on Reddit's "daily programmer" subreddit a few months back, never found a great approach other than brute force (along with trying to identify unique/expensive sequences). Do you see it as a variation on the one in the article? https://www.reddit.com/r/dailyprogrammer/comments/8rcjx0/20180615_challenge_363_hard_anagram_slices/ https://www.reddit.com/r/dailyprogrammer/comments/8rcjx0/201... "Given an input set of strings, produce an output string. Every string in the input must be an anagram of some slice of the output. A slice in this context is a series of characters from the string separated by a fixed amount (i.e. anything that can be formed using Python's s[a:b:c] syntax). It's different from a substring in that you're allowed to skip characters, as long as you skip the same number of characters on each step."

robinhouston 8y ago
Interesting problem! It’s a variant of the Shortest Superstring Problem, which is known to be NP-hard. I bet this variant is NP-hard as well. Obviously that doesn’t mean we can’t find nice algorithms that work well in particular cases, but I bet it’s hard to prove that a solution is the best possible. What makes the minimal superpermutation problem different is that we’re trying to pack together the set of ALL permutations of some number of symbols, so the set of strings has a lot of known symmetry and structure we can take advantage of. In this case I hope it will be possible to find a general solution that we can prove is the best possible.