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
What you are trying to do is get all the permutations of a collection. Unique permutations of list permutations of k objects from a set of n algorithm Here is the code snippet: static void Main(string[] args) { var list = new List<string> { “a”, “b”, “c”, “d”, “e” }; var result = GetPermutations(list, 3); … 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
9 min, including test import math def nthperm(li, n): n -= 1 s = len(li) res = [] if math.factorial(s) <= n: return None for x in range(s-1,-1,-1): f = math.factorial(x) d = n / f n -= d * f res.append(li[d]) del(li[d]) return res #now that’s fast… nthperm(range(40), 123456789012345678901234567890)
ChrisB solution had a mistake, he wasn’t caching the length of the loop before the arr.shift, and it was not returning the last combination, I think this will do the job: function getCombinations (arr, n) { var i, j, k, elem, l = arr.length, childperm, ret = []; if (n == 1){ for (i = … Read more
We can use the bijection mentioned in the wikipedia article, which maps combinations without repetition of type n+k-1 choose k to k-multicombinations of size n. We generate the combinations without repetition and map them using bsxfun(@minus, nchoosek(1:n+k-1,k), 0:k-1);. This results in the following function: function combs = nmultichoosek(values, k) %// Return number of multisubsets or … Read more
Slight reformulation of cgeers answer to get you the tuples you want instead of arrays: var combinations = from item1 in list from item2 in list where item1 < item2 select Tuple.Create(item1, item2); (Use ToList or ToArray if you want.) In non-query-expression form (reordered somewhat): var combinations = list.SelectMany(x => list, (x, y) => Tuple.Create(x, … Read more
The complexity is O(C(n,k)) which is O(n choose k). This ends up being equivalent to O(min(n^k, n^(n-k))).
>>> def pascal(n): … line = [1] … for k in range(n): … line.append(line[k] * (n-k) / (k+1)) … return line … >>> pascal(9) [1, 9, 36, 84, 126, 126, 84, 36, 9, 1] This uses the following identity: C(n,k+1) = C(n,k) * (n-k) / (k+1) So you can start with C(n,0) = 1 and … Read more