Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Generating all permutations, combinations, and power set of a string (2012)

exceptional-code.blogspot.com

Post reply on HN
Print view View original

21–30 of 48 posts

Re: Generating all permutations, combinations, and power set of a string (2012)

#21

Post by Scea91 »

bluetwo wrote: post #9

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.

It is true that due to complexity reasons,enumerating all combinations is usually avoided. However, in my opinion it is useful to know how to do things the basic way when learning more advanced algorithms such as RANSAC, APRIORI and others...

Re: Generating all permutations, combinations, and power set of a string (2012)

#22

Post by taeric »

RodgerTheGreat wrote: post #5

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 Set > power(List a) { return IntStream.range(0, 1 IntStream.range(0, a.size()) .filter(y -> (1 a.get(y)) .collect(Collectors.toSe…

If you enjoy this sort of thing, it is also the start of Knuth's volume 4. In it, he goes over many different schemes of generating things.

My favorites are the ones he calls "loopless" since they do not have a loop during each iteration of the algorithm. So, in this example, there is no need for the filter line that will ultimately have to loop (or hash or something else not trivial) to find the items to filter out). In particular, to generate all permutations of binary digits requires something like 4 assignments and one test for each iteration.

The ridiculously interesting ones are based on De Bruijn sequences. Basically, think if you have a combination lock that constantly shifts in 1 character when you type. Is it possible to test all combinations of digits without "wasting" a keypress?

Re: Generating all permutations, combinations, and power set of a string (2012)

#24

Post by [deleted] »

RodgerTheGreat wrote: post #5

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 Set > power(List a) { return IntStream.range(0, 1 IntStream.range(0, a.size()) .filter(y -> (1 a.get(y)) .collect(Collectors.toSe…

[deleted]

Re: Generating all permutations, combinations, and power set of a string (2012)

#25

Post by Johnny_Brahms »

forinti wrote: post #10
helicon wrote: post #7

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.

There was a recent post about anagrams and the author just put all the letters in alphabetical order and then compared the words, which was more efficient than generating permutations.

I ran an anagram website in the 90s, and that was what we did. We stored word lists with a key of all their letters sorted. We then calculated anagram scores on demand because I couldn't work out a nice enough way to store those.

We had about 300 hits/day so it didn't matter.

Re: Generating all permutations, combinations, and power set of a string (2012)

#26

Post by bogomipz »

RodgerTheGreat wrote: post #5

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 Set > power(List a) { return IntStream.range(0, 1 IntStream.range(0, a.size()) .filter(y -> (1 a.get(y)) .collect(Collectors.toSe…

>"For each item of a set, you will either include it or exclude it in one of the results."

I found this interesting. This may be a silly question(my combinatorics knowledge is limited) but what exactly is the relationship between power sets and "N choose K"?

Re: Generating all permutations, combinations, and power set of a string (2012)

#28

Post by cpchen »

bogomipz wrote: post #26
RodgerTheGreat wrote: post #5

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 Set > power(List a) { return IntStream.range(0, 1 IntStream.range(0, a.size()) .filter(y -> (1 a.get(y)) .collect(Collectors.toSe…

>"For each item of a set, you will either include it or exclude it in one of the results." I found this interesting. This may be a silly question(my combinatorics knowledge is limited) but what exactly is the relationship between power sets and "N choose K"?

The classic recurrence is if you're choosing K elements out of N, it either has the first element (in which case you choose K-1 elements out of the remaining N-1) or it doesn't (in which case you choose K elements out of the remaining N-1), so:

N choose K = (N-1 choose K-1) + (N-1 choose K).

Also, if you sum (N choose K) for all values of K you get 2^N.

Re: Generating all permutations, combinations, and power set of a string (2012)

#29

Post by bmm6o »

bogomipz wrote: post #26
RodgerTheGreat wrote: post #5

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 Set > power(List a) { return IntStream.range(0, 1 IntStream.range(0, a.size()) .filter(y -> (1 a.get(y)) .collect(Collectors.toSe…

>"For each item of a set, you will either include it or exclude it in one of the results." I found this interesting. This may be a silly question(my combinatorics knowledge is limited) but what exactly is the relationship between power sets and "N choose K"?

The combinations (n choose k) tell you how many ways there are to take k things from n, and so count that subset of the power set. And since the sets of k things are obviously distinct from the sets of j != k things, there is no overlap. This gives the well-known result that 2^n = Sum n choose k.

Re: Generating all permutations, combinations, and power set of a string (2012)

#30

Post by rajathagasthya »

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:])
Post reply on HN