Reduced permutations

Question

Consider the following string

abcd

I can return 2 character permutations (cartesian product) like this

$ echo {a,b,c,d}{a,b,c,d}
aa ab ac ad ba bb bc bd ca cb cc cd da db dc dd

However I would like to remove redundant entries such as

ba ca cb da db dc

and invalid entries

aa bb cc dd

so I am left with

ab ac ad bc bd cd

Example

Answer 1

I realized that I am not looking for permutations, but the power set. Here is an implementation in Awk:

{
  for (c = 0; c < 2 ^ NF; c++) {
    e = 0
    for (d = 0; d < NF; d++)
      if (int(c / 2 ^ d) % 2) {
        printf "%s", $(d + 1)
      }
    print ""
  }
}

Input:

a b c d

Output:

a
b
ab
c
ac
bc
abc
d
ad
bd
abd
cd
acd
bcd
abcd

Example