41–48 of 48 posts
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:])
There might be a way to avoid messing with the recursive depth if you swapped out the main part of the for loop for a generator though.
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…
* routine stolen from gimpel
* algorithm from peck and schrack
define('p(s)t,n,c,k','p_init') :(p_end)
p_init n = size(s)
r = array('2:' n, 0)
&alphabet len(n) . y
x = array('2:' n, y)
k = n + 1
p_0 k = k - 1
x[k] len(1) . s1 tab(k) . s2 = s2 s1 :s(p_0)
define('p(s)i,k')
p = s :(return)
p k = size(s)
p_1 s = replace(x[k],y,s) :f(p_2)
r[k] = r[k] + 1
k = eq(remdr(r[k], k),0) k - 1 :s(p_1)
p = s :(return)
p_2 define('p(s)t,n,s1,s2','p_init') :(freturn)
p_end
* example: all permutations of string abcdefgh
s = 'abcdefgh'
abc output = p(s) :s(abc)f(end)
end
define('r(s,ors)c,f,s1,a,d,os')
:(r_end)
r ors rtab(1) len(1) . c :f(freturn)
s (span(c) | null) . f =
s arb . s1 len(1) . d c = :f(r_1)
r = s1 f c d s :(return)
r_1 ors break(c) . os
r = r(s,os) f :s(return)f(freturn)
r_end
s = 'abcdefgh'
output = s
x01 output = r(output,s) :s(x01)
endPython 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 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:])
An iterative Python recipe can be found in the docs: https://docs.python.org/3/library/itertools.html#itertools.p...
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.
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.
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:])
Wouldn't you hit Python's recursive limit rather quickly doing this? There might be a way to avoid messing with the recursive depth if you swapped out the main part of the for loop for a generator though.
In Haskell: import Data.List ( subsequences ) powerset = subsequences
It doesn't contribute much to the conversation to note that your favorite language has a canned procedure for solving an algorithmic problem like this. If you're genuinely interested in demonstrating Haskell's capabilities it would be far more constructive to offer an implementation of such a routine, that it might be compared directly to the others in the article and this thread.