The simplest approach is as follows: Sort the list: O(n lg n) The sorted list is the first permutation Repeatedly generate the “next” permutation from the previous one: O(n! * <complexity of finding next permutaion>) Step 3 can be accomplished by defining the next permutation as the one that would appear directly after the current … Read more
While Stefan and Matt make a good point about using Heap’s algorithm, I think you have an important question about why your code doesn’t work and how you would debug that. In this case, the algorithm is simply incorrect, and the best way to discover that is with pencil and paper IMO. What you are … Read more
if n is not far from r then using the recursive definition of combination is probably better, since xC0 == 1 you will only have a few iterations: The relevant recursive definition here is: nCr = (n-1)C(r-1) * n/r This can be nicely computed using tail recursion with the following list: [(n – r, 0), … Read more
You don’t need to know n in advance to use itertools.product >>> import itertools >>> s=[ [ ‘a’, ‘b’, ‘c’], [‘d’], [‘e’, ‘f’] ] >>> list(itertools.product(*s)) [(‘a’, ‘d’, ‘e’), (‘a’, ‘d’, ‘f’), (‘b’, ‘d’, ‘e’), (‘b’, ‘d’, ‘f’), (‘c’, ‘d’, ‘e’), (‘c’, ‘d’, ‘f’)]
The question is theoretical but you can do it in O(n) time and o(1) space. Allocate an array of 232 counters and set them all to zero. This is O(1) step because the array has constant size. Then iterate through the two arrays. For array A, increment the counters corresponding to the integers read. For … Read more
Historical prologue The Wikipedia article on Heap’s algorithm has been corrected, defaced and corrected again several times since this answer was written. The version referred to by the question and original answer was incorrect; you can see it in Wikipedia’s change history. The current version may or may not be correct; at the time of … Read more
There is a trivial O(n^2) algorithm, but you can do this in O(n). E.g.: A = [a, b, c, d, e] P = [4, 3, 2, 0, 1] We can swap each element in A with the right element required by P, after each swap, there will be one more element in the right position, … Read more
itertools.permutations(my_list, 3)
Using STL: Permutation: using std::next_permutation template <typename T> void Permutation(std::vector<T> v) { std::sort(v.begin(), v.end()); do { std::copy(v.begin(), v.end(), std::ostream_iterator<T>(std::cout, ” “)); std::cout << std::endl; } while (std::next_permutation(v.begin(), v.end())); } Combination: template <typename T> void Combination(const std::vector<T>& v, std::size_t count) { assert(count <= v.size()); std::vector<bool> bitset(v.size() – count, 0); bitset.resize(v.size(), 1); do { for (std::size_t i … Read more
A recursive solution to find k-subset permutations (in pseudo-code): kSubsetPermutations(partial, set, k) { for (each element in set) { if (k equals 1) { store partial + element } else { make copy of set remove element from copy of set recurse with (partial + element, copy of set, k – 1) } } } … Read more