How to generate all possible combinations of lines in a file using Bash?

Reusing the get_combs() function from https://stackoverflow.com/a/56916316/1745001:

$ cat tst.awk
###################
# Calculate all combinations of a set of strings, see
# https://rosettacode.org/wiki/Combinations#AWK
###################

function get_combs(A,B, i,n,comb) {
    ## Default value for r is to choose 2 from pool of all elements in A.
    ## Can alternatively be set on the command line:-
    ##    awk -v r=<number of items being chosen> -f <scriptname>
    n = length(A)
    if (r=="") r = 2

    comb = ""
    for (i=1; i <= r; i++) { ## First combination of items:
        indices[i] = i
        comb = (i>1 ? comb OFS : "") A[indices[i]]
    }
    B[comb]

    ## While 1st item is less than its maximum permitted value...
    while (indices[1] < n - r + 1) {
        ## loop backwards through all items in the previous
        ## combination of items until an item is found that is
        ## less than its maximum permitted value:
        for (i = r; i >= 1; i--) {
            ## If the equivalently positioned item in the
            ## previous combination of items is less than its
            ## maximum permitted value...
            if (indices[i] < n - r + i) {
                ## increment the current item by 1:
                indices[i]++
                ## Save the current position-index for use
                ## outside this "for" loop:
                p = i
                break}}
        ## Put consecutive numbers in the remainder of the array,
        ## counting up from position-index p.
        for (i = p + 1; i <= r; i++) indices[i] = indices[i - 1] + 1

        ## Print the current combination of items:
        comb = ""
        for (i=1; i <= r; i++) {
            comb = (i>1 ? comb OFS : "") A[indices[i]]
        }
        B[comb]
    }
}

# Input should be a list of strings
{ A[NR] = $0 }
END {
    OFS = ","
    for (r=NR; r>=2; r--) {
        delete B
        get_combs(A,B)
        PROCINFO["sorted_in"] = "@ind_str_asc"
        for (comb in B) {
            print comb
        }
    }
}

$ awk -f tst.awk test.txt
A,B,C
A,B
A,C
B,C

with the binary counter trick to iterate all subsets...

$ awk '{a[NR]=$1}
   END {for(i=0;i<2^NR;i++)
          {printf "{";
           for(j=0;j<NR;j++) printf "%s", and(i,2^j)?FS a[j+1]:"";
           print " }"}}' file


{ }
{ A }
{ B }
{ A B }
{ C }
{ A C }
{ B C }
{ A B C }
{ D }
{ A D }
{ B D }
{ A B D }
{ C D }
{ A C D }
{ B C D }
{ A B C D }

In the desired format, pipe to another awk to filter n<2 elements

awk -v FS=, '{a[NR]=$1}
         END {for(i=0;i<2^NR;i++)
             {s=""; 
              for(j=0;j<NR;j++) 
                {e=and(i,2^j); 
                 printf "%s", e?s a[j+1]:""; if(e)s=FS}
              print comb}}' file | 
awk -F, 'NF>1'


A,B
A,C
B,C
A,B,C
A,D
B,D
A,B,D
C,D
A,C,D
B,C,D
A,B,C,D

How does it work?

All combinations are equivalent to all subsets of the given elements. This in turn can be enumerated (tagged) with 0..2^n-1. If we represent the enumeration counter in binary, each position bit can be mapped to an element of the full set. So when running the enumeration on all subsets we can create a particular subset with the elements where the corresponding bit is set for a given tag.

For example for a 3 element initial set {A,B,C}. We have the enumeration

0 0 0   -> no elements, empty subset  -> { }
0 0 1   -> A bit is set               -> { A }
0 1 0   -> B bit is set               -> { B }
0 1 1   -> Both A and B bits are set  -> { A B }
... etc

the rest is just formatting.

This method is good for generating all combinations, for various constraints which will reduce the choices (e.g. exactly 3 elements) this is not very efficient. Also, there is an upper bound for N, due to 2^N.

We can use the following awk to get each possible combination of all the lines:

awk 'NR==FNR { a[$0]; next } { for (i in a) print i, $0 }' test.txt test.txt

Then, we can use split to write each line into a seperate file:

awk 'NR==FNR { a[$0]; next } { for (i in a) print i, $0 }' test.txt test.txt > tmp.txt
split -l 1 -d tmp.txt "test-"
rm tmp.txt

Example on my local machine:

$
$ cat test.txt
A
B
C
$
$ awk 'NR==FNR { a[$0]; next } { for (i in a) print i, $0 }' test.txt test.txt > tmp.txt
$ split -l 1 -d tmp.txt "test-"
$ rm tmp.txt
$
$ tail -n +1 *
==> test-00 <==
A A

==> test-01 <==
B A

==> test-02 <==
C A

==> test-03 <==
A B

==> test-04 <==
B B

==> test-05 <==
C B

==> test-06 <==
A C

==> test-07 <==
B C

==> test-08 <==
C C

==> test.txt <==
A
B
C
$

A bash recursive function: this won't be the fastest solution

all_combinations() {
    (($# == 0)) && return
    (IFS=,; echo "$*")
    local i x
    for ((i=0; i<$#; i++)); do 
        x=("$@")
        unset 'x[i]'
        "${FUNCNAME[0]}" "${x[@]}"
    done
}

combinations() {
    all_combinations "$@" |
      grep , |                      # at least 2 element
      sort -u |                     # remove duplicates
      while IFS= read -r line; do   # print number of elements
          printf '%d\t%s\n' \
            $(commas=${line//[^,]/}; echo ${#commas}) \
            "$line"
      done |
      sort -k1,1nr -k2 |            # sort by num + line
      cut -f2-                      # remove num
}

mapfile -t lines < test.txt
combinations "${lines[@]}"

if test.txt contains 4 lines, this produces

A,B,C,D
A,B,C
A,B,D
A,C,D
B,C,D
A,B
A,C
A,D
B,C
B,D
C,D

Assumptions:

• the string A,B,C is considered to be equivalent to A,C,B, B,A,C, B,C,A, C,A,B and C,B,A (ie, we only need to generate one of these 6 combinations)

One idea for generating a list of combinations ...

• we'll load lines into an array
• for each item in the array we'll start a new set of output strings
• make recursive calls to append the next array item to our output string
• as we're appending array items to the output we'll go ahead and print each string that consists of 2 or more array items
• this is more of a tail recursion method which should eliminate the generation of duplicates (A,B,C vs the other 5 equivalent patterns) and/or or the need to rollback "already seen' combos

One awk idea for implementing this logic:

awk '

# input params are current output string, current arr[] index, and current output length (ie, number of fields)
# parameter "i" will be treated as a local variable

function combo(output, j, combo_length,  i) {

    if ( combo_length >= 2)           # print any combination with a length >= 2
       print output

    for (i=j+1; i<=n; i++)            # loop through "rest" of array entries for next field in output
        combo(output "," arr[i], i, combo_length+1 )
}

    { arr[NR]=$1 }                     # load fields into array "arr[]"

END { n=length(arr)

      for (i=1; i<=n; i++)             # for each arr[i] start a new set of combos starting with arr[i]
          combo(arr[i],i,1)
    }
' test.txt

This generates:

A,B
A,B,C
A,B,C,D
A,B,D
A,C
A,C,D
A,D
B,C
B,C,D
B,D
C,D

If we want to sort based on number of fields and then the output string we can make the following change:

• change print output to print combo_length, output and then ...
• pipe the awk output through sort | cut (we'll borrow glenn's code here)

This generates:

$ awk ' ... print combo_length,output ...' test.txt |  sort -k1,1nr -k2 | cut -d" " -f2-

A,B,C,D
A,B,C
A,B,D
A,C,D
B,C,D
A,B
A,C
A,D
B,C
B,D
C,D

For a 20-line test.txt ( letters A to T) with the output dumped to file test.out:

$ time awk '...' test.txt > test.out

real    0m1.420s
user    0m1.279s
sys     0m0.139s

$ wc -l test.out
 1048555  2097110 23685256 test.out

$ time awk '...' test.txt | sort ... | cut ... > test.out

real    0m3.456s
user    0m3.493s
sys     0m0.185s

$ wc test.out
 1048555  1048555 20971480 test.out