Generating all permutations, combinations, and power set of a string (2012) (opens in new tab)

There's a simple iterative alternative for generating power sets. For each item of a set, you will either include it or exclude it in one of the results. If you count from 0 to 2^n, the binary digits of your counter will enumerate every combination of these possibilities. In Java 8:

    static <T> Set<Set<T>> power(List<T> a) {
      return IntStream.range(0, 1 << a.size())
      .mapToObj(x -> IntStream.range(0, a.size())
        .filter(y -> (1 << y & x) != 0)
        .mapToObj(y -> a.get(y))
        .collect(Collectors.toSet())
      ).collect(Collectors.toSet());
    }

In JS/ES6:

    function power(a) {
      var r = [];
      for(var x = (1 << a.length) - 1; x >= 0; x--) {
        r.push(a.filter((y, i) => 1 << i & x));
      }
      return r;
    }

In K6:

    {x@&:'+!(#x)#2}

Posts like this are why I love HN. I recently wrote a program to find anagrams of a given string (a Countdown solver if you live in the UK).

It includes a really naive method for generating all possible permutations of the string, but reading this post I can immediately see a far better way to do it.

That's my weekend taken care of! thanks to the poster and author.

Python recursive solution for generating permutations:

  s = 'abcd'
  prefix = ''
  permutation(prefix, s)

  def permutation(prefix, s):
      n = len(s)
      if n == 0:
          print(prefix)
      else:
          for i in range(n):
              permutation(prefix + s[i], s[:i] + s[i+1:])

In Haskell:

    import Data.List ( subsequences )
    powerset = subsequences

If anyone wants to know how deep down the rabbit hole this stuff goes, they should read this blog post [1] on writing a Levenshtein Automaton to speed up fuzzy matching in Lucene by 100 times. It gets deep!

[1]: http://blog.mikemccandless.com/2011/03/lucenes-fuzzyquery-is...

I am curious where you would use something like this. I've worked with Minimum Edit Distance, which is similar (what is the minimum number of steps to convert one string into another).

Not sure where you would need to pull together all variations of the string and apply it to a problem.

imo the coolest way to generate permutations https://en.m.wikipedia.org/wiki/Factorial_number_system

I prefer the use of iterators, instead of generating a whole collection. An example of a permutation iterator in C++ is:

    class Permutations
    {
    public:
        Permutations(int val_n) : n(val_n), _more(true)
        {
            a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = i;
        }
        ~Permutations()
        {
            delete []a;
        }
        bool more() { return _more; }
        void next()
        {
            _more = false;
            for (int i = n-2; i >= 0; i--)
                if (a[i] < a[i+1])
                {
                    _more = true;
                    for (int j = n-1; j > i; j--)
                        if (a[j] > a[i])
                        {
                            swap(a[j], a[i]);
                            break;
                        }
                    i++;
                    for (int j = n-1; j > i; j--, i++)
                        swap(a[j], a[i]);
                    break;
                }
        }
        int operator[](int i) { return a[i]; }
            
        int n;
    private:
        void swap(int &x, int &y)
        {
            int h = x;
            x = y;
            y = h;
        }
        bool _more;
        int *a;
    };

You can use binary to help generate your combinations of k elements (every number of n bits with k 1s represents a combination of n-choose-k): http://alquerubim.blogspot.com.br/2012/05/combinacoes-de-dig...

And you can use factoradics to generate your permutations (because the leftmost digit tells you which is the next element): http://alquerubim.blogspot.com.br/2012/06/combinacoes-de-dig...

So you transform your problem into counting. You just have to choose a suitable base.

Python standard lib...

  import itertools
  list(itertools.permutations('abc'))

Nice post. I don't know why there is no a bigger push in experiments/investigations with tree-like massive combinatorial expansion with lazy-evaluation, so the solution space can be somewhat "reasonable" (e.g. assuming you have infinite combinatorial expansion capability, adding restrictions, so once you start the evaluation most of the combinations get discarded, so you'll have to deal with a "sparse combinatorial expansion" analog to a convex space for solutions in geometry).

In Java there are libraries for this (as with most things): https://github.com/tomgibara/permute

I don't know how efficient it is, but the bsd glob() function in their c stdlib can generate unique permutations with brace syntax. If you wanted all permutations of "abc", you would pass it "{a,b,c}{a,b,c}{a,b,c}"

It's also easy to get to bsd's glob() on non-bsd platforms with Perl:

  perl -MFile::Glob=bsd_glob -e 'print bsd_glob("{a,b,c}{a,b,c}{a,b,c}\n");'

Note the sub-optimality of generatePermutations.

For the second but last level (which will be entered n! times) it is doing n iterations which gives us a (not so tight) lower bound of n * n! instead of the optimal n!.

The issue is the use of an array for visited instead of, say, a linked list where each level gets a list of only unvisited nodes.

Very nice, thank you for sharing!

For comparison, here are Prolog solutions for these tasks.

The first building block is a relation between a list, one of its elements, and the list of remaining elements:

    list_element_rest([E|Ls], E, Ls).
    list_element_rest([L|Ls0], E, [L|Ls]) :-
            list_element_rest(Ls0, E, Ls).

In the following, I assume you have set double_quotes to chars, so that you can easily work on a string as a list of characters:

    :- set_prolog_flag(double_quotes, chars).

Here is a sample interaction, using this relation:

    ?- list_element_rest("abc", E, Ls).
    E = a,
    Ls = [b, c] ;
    E = b,
    Ls = [a, c] ;
    E = c,
    Ls = [a, b] ;
    false.

Importantly, we can use it in all directions, for example also to insert an element into a list:

    ?- list_element_rest(Ls, a, "bc").
    Ls = [a, b, c] ;
    Ls = [b, a, c] ;
    Ls = [b, c, a] ;
    false.

Using list_element_rest/3 as a building block, we can define the relation between a list and one of its permutations as follows:

    list_permutation([], []).
    list_permutation([L|Ls], Ps) :-
            list_permutation(Ls, Ps0),
            list_element_rest(Ps, L, Ps0).

This completes the first task. Example:

    ?- list_permutation("abc", Ps).
    Ps = [a, b, c] ;
    Ps = [b, a, c] ;
    Ps = [b, c, a] ;
    Ps = [a, c, b] ;
    Ps = [c, a, b] ;
    Ps = [c, b, a] ;
    false.

In many Prolog implementations, this predicate is already implemented as permutation/2, but the point here is to show that you can also implement it easily yourself, at least in the input->output direction, where the first argument is fully instantiated.

To solve both the second and third task, let us relate a list to one of its subsequences:

    subseq([]) --> [].
    subseq([L|Ls]) --> ([] | [L]), subseq(Ls).

With this definition, you can for example get all 2-element combinations of "abcd" as follows:

    ?- length(Ls, 2), phrase(subseq("abcd"), Ls).
    Ls = [c, d] ;
    Ls = [b, d] ;
    Ls = [b, c] ;
    Ls = [a, d] ;
    Ls = [a, c] ;
    Ls = [a, b] ;
    false.

The powerset is a natural generalization of this query, where you simply omit the first goal:

    ?- phrase(subseq("abcd"), Ls).
    Ls = [] ;
    Ls = [d] ;
    Ls = [c] ;
    Ls = [c, d] ;
    Ls = [b] ;
    Ls = [b, d] ;
    Ls = [b, c] ;
    Ls = [b, c, d] ;
    Ls = [a] ;
    Ls = [a, d] ;
    Ls = [a, c] ;
    Ls = [a, c, d] ;
    Ls = [a, b] ;
    Ls = [a, b, d] ;
    Ls = [a, b, c] ;
    Ls = [a, b, c, d].

Generating necklaces and bracelets is fun too, see eg. http://www.sciencedirect.com/science/article/pii/S0304397512...

Thanks! I've been looking into this topic and the article is very helpful.

ha, fun.. I used to choke so much on powersets, after reading a lot I finally got the recursive version; here in python (I know, but I couldn't find back my lisp/ml version so..)

https://gist.github.com/agumonkey/6ab51dfa759ef1993c55

Interesting thread.

Apropos of permutations, I had written these two posts a few months ago:

Permutation facts:

https://jugad2.blogspot.in/2016/10/by-vasudev-ram-nicomachus...

perm_facts version with list comps and functional programming:

https://jugad2.blogspot.in/2016/10/permfacts-version-with-li...

The first post above also has some interesting facts about factorials, their occurrences and applications, which was a revelation to me.