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());
    }

    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;
    }

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

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;
    };

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...

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.

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:])

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

undefined

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).

    :- set_prolog_flag(double_quotes, chars).

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

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

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

    ?- 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.

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).

    ?- 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.

    ?- 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...

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.

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

undefined

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

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

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.

In Haskell:

    import Data.List ( subsequences )
    powerset = subsequences