Re^4: Challenge: Generate a glob patterns from a word list (UPDATE)

> My guess is that it is horribly explosive in N.

I doubt it.

Intuitively I'd say a two phase approach should work.

Build a tree like with a Trie
Parse the tree bottom-up and collapse it into a graph by using look-up hashes for duplicated sub-trees

Since a Trie-tree isn't "exploding", this should be safe.

Untested, of course.

Sorry, I should have read the examples in the OP more closely.

I wasn't aware that

Without that my approach above should work.

Now I'm rather pessimistic.

Cheers Rolf
_{(addicted to the Perl Programming Language :)

Wikisyntax for the Monastery}

Comment on Re^4: Challenge: Generate a glob patterns from a word list (UPDATE) Select or Download Code

Replies are listed 'Best First'.
Re^5: Challenge: Generate a glob patterns from a word list by choroba (Cardinal) on May 04, 2021 at 18:50 UTC
Maybe a suffix tree could help? `map{substr$_->[0],$_->[1]\|\|0,1}[\\|\|{},3],[[]],[ref qr-1,-,-1],[{}],[sub{}^ARGV,3]`	[reply] [d/l]
Re^6: Challenge: Generate a glob patterns from a word list by LanX (Saint) on May 05, 2021 at 11:36 UTC
Please see my update here, that's more complicated than I thought. This reminds me of what my prof called a "Minimales Wort Problem" in my studies, but I couldn't find a link for it. Basically finding the shortest algebraic term expressing a solution, the `{,a,b}` clauses are operations here. Problem now is that I doubt that there is always a unique minimal solution, which can be reached by a path of successive optimization steps. This means you have to try different steps in different order, which will indeed explode the complexity. Cheers Rolf _{(addicted to the Perl Programming Language :) Wikisyntax for the Monastery}	[reply] [d/l]