5

I was doing research on how to generate all non-repeating permutations of a set of a numbers without using recursion in Bash and I found this answer that worked, but I want to understand why.

Say you have three numbers: 1, 2, 3.

The following command will generate all possible non-repeating permutations:

printf "%s\n" {1,2,3}{1,2,3}{1,2,3} | sort -u | sed '/\(.\).*\1/d'
123
132
213
231
312
321

I understand what the printf with %s does when the argument is the brace expansions of the set {1, 2, 3} three times (which would print every single possible outcome).

I know that sort -u will output only unique lines.

I know that sed /<pattern>/d is used to delete any lines that match <pattern>.

Reading the pattern within the sed, I am somewhat confused. I know how to read regex but I don't see how this pattern works within the sed command.

\( = literal '('
.  = any character, once
\) = literal ')'
.* = any character, zero or more times
\1 = reference to first captured group

How does then the sed command remove non-unique values from this regex pattern? I don't understand how there's a reference to a captured group, when there's not really one? The parentheses are being used in the pattern to be matched literally? Everything about this execution makes sense to me until the sed command.

  • 3
    Sed uses basic regular expressions (BRE) by default - so \(.\) is in fact a capture group (otherwise \1 would result in a Invalid back reference error) – steeldriver Jul 10 at 22:30
  • 1
    The output is already unique, no need to sort it. – Freddy Jul 10 at 22:36
  • The sort -u doesn't actually change the piped input to sed at all. Compare the output of printf "%s\n" {1,2,3}{1,2,3}{1,2,3} | sort -u with the output of just printf "%s\n" {1,2,3}{1,2,3}{1,2,3} The outputs are exactly the same (at least on OSX). – Greenonline Jul 11 at 17:11
4

That's basic regular expressions (BRE) for sed by default, so \(.\) is a capture group containing any one character. Then the .* just skips everything, and \1 matches whatever the group matched. If the whole lot can be made to match, then some character showed up twice, once for the group, and once for the backreference.

In fact, if I'm not mistaken, that wouldn't even work with standard extended regular expressions, since (for whatever reasons) backreferences aren't supported in them. Backreferences are only mentioned under "BREs matching multiple characters", not under EREs, and in fact the same thing with ERE doesn't work on my macOS (it takes the \1 as meaning a literal number 1):

$ printf "%s\n" 122 321 | sed -E -e '/(.).*\1/d'
122

GNU tools do support backreferences in ERE, though.

(I don't think sort -u is necessary here, the combination of brace expansions should produce all combinations without duplicates.)

| improve this answer | |
  • 1
    Ohhhhh, so if the parentheses indeed are capturing a pattern and then there's a back reference, then the whole thing then becomes, if any one character, followed by zero or more characters, followed by the first captured character matches, delete. Therefore, permutations like 111 112 122 221 would be deleted since (1)1(1) would be matched, (1)-(1)2 [* = zero or more, so zero cases in this permutation], etc, etc, etc. That makes more sense now. – AnthonyBB Jul 10 at 22:50
  • @AnthonyBB, yes, exactly – ilkkachu Jul 10 at 22:52
  • I'm so used to ERE that forgot BRE was the default for sed and special regex characters only take a special meaning in BRE if prefixed with a \, while in ERE, they are special until they are escaped with \. Thank you! – AnthonyBB Jul 10 at 23:01
  • 1
    Yes, back-references seem to be UN-supported in POSIX EREs, but have been historically supported in sed all the time on the right side of an s/// replacement and, by extension, in most implementations, directly on a simple regex. Search for [[2addr]s/BRE/replacement/flags](pubs.opengroup.org/onlinepubs/9699919799/utilities/sed.html) or simply for back-references. In practice it is rare that back-references are not available. – Isaac Jul 11 at 2:43
  • 1
    @Isaac, I've also understood that regexes with backreferences aren't an actual regular language any more, and that supporting backreferences precludes some efficient RE implementations, but it might be that capture groups have the same effect. I'm not sure, though, I'm an engineer, not a comp.sci major. ;) – ilkkachu Jul 11 at 11:59
5

As a first step, you need to understand \(.\) correctly. In basic regular expressions, it is a capture group capturing any character, that must be reproduced by \1. Those are not literal parenthesis.


Now, for the extremely cool part! What does each element of the regex match in each case?

     Left  \(.\)  .*  \1  Right  Result
111        1      1   1          Deleted!
112        1          1   2      Deleted!
113        1          1   3      Deleted!
121        1      2   1          Deleted!
122  1     2          2          Deleted!
123        ?      ?   ?          NoMatch
131        1      3   1          Deleted!
132        ?      ?   ?          NoMatch
133  1     3          3          Deleted!      

On the 122, if not clear: Since the expression is not anchored, 1 goes away to the left, the middle 2 matches the capture group \(.\) and the last 2 matches the backreference \1. .* (the zero-or-more characters matching regex) will do its best to fit the string, so in this case it contracts to the null string.

If you doubt it, try

echo 122 | grep --color=always '\(.\).*\1'

You will see that only the 22 has been colored.


Compare it with the anchored version of the regex:

$ printf "%s\n" {1,2,3}{1,2,3}{1,2,3} | sort -u | sed '/^\(.\).*\1$/d'
112
113
122
123
132
133
...

Now there are not "Left" and "Right" slots:

     ^\(.\)  .*  \1$  Result
111  1       1   1    Deleted!
112  ?       ?   ?    NoMatch
113  ?       ?   ?    NoMatch
121  1       2   1    Deleted!
122  ?       ?   ?    NoMatch
123  ?       ?   ?    NoMatch
131  1       3   1    Deleted!
132  ?       ?   ?    NoMatch
133  ?       ?   ?    NoMatch

The 1st digit must be the last digit in this version, so there are less matches.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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