CODEWITHSUNDEEP
arraysshellbrace-expansion
Elle Fie
Elle Fie

Reputation: 691

Reversing shell-style brace expansion

Brace expansion takes a pattern and expands it. For example:

sp{el,il,al}l

Expands to:

spell spill spall

Is there an algorithm (potentially with a JavaScript implementation) to do the reverse in a way that minimizes the constructed string?

i.e., take in an array [spell spill spall] and return a string "sp{e,i,a}ll"

Upvotes: 4

Views: 468

Answers (2)

Alex Willmer
Alex Willmer

Reputation: 564

As requested in the original question, node-brace-compression contains a JavaScript implementation. E.g.

var compress = require('brace-compression');
var data = [
  'foo-1',
  'foo-2',
  'foo-3'
];

console.log(compress(data));
// => "foo-{1..3}"

Upvotes: 1

xhienne
xhienne

Reputation: 6144

Minimizing the resulting string can be done in many different ways, but since you mention Bash, I'll choose the Bash way which is not the most optimized one.

Yes, there is a Bash way! Bash creators have included it as the readline command complete-into-braces. When using Bash interactively, if you hit Meta{ (which is either Alt{ or Esc-then-{ on my machine), all possible completions are grouped into one single brace expansion.

$ echo /usr/
bin/     games/   include/ lib/     local/   sbin/    share/   src/  

$ echo /usr/{bin,games,include,l{ib,ocal},s{bin,hare,rc}}

Above, the first time I hit Tab to show all possible completions, and the second time I hit Alt{.

Back to your question: you are looking for an algorithm. Obviously you may find something in Bash source code. The function you are looking for is really_munge_braces() in bracecomp.c

Upvotes: 4

Related Questions