Look at the powerset() recipe in the itertools docs. from itertools import chain, combinations def powerset(iterable): “powerset([1,2,3]) –> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)” s = list(iterable) return chain.from_iterable(combinations(s, r) for r in range(len(s)+1)) def subsets(s): return map(set, powerset(s))
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
Say you have n letters (or students, or whatever), and every week want to partition them into subsets of size k (for a total of n/k subsets every week). This method will generate almost n/k subsets every week – I show below how to extend it to generate exactly n/k subsets. Generating the Subsets (no … Read more
Recursion can solve this problem neatly: function callManyTimes(maxIndices, func) { doCallManyTimes(maxIndices, func, [], 0); } function doCallManyTimes(maxIndices, func, args, index) { if (maxIndices.length == 0) { func(args); } else { var rest = maxIndices.slice(1); for (args[index] = 0; args[index] < maxIndices[0]; ++args[index]) { doCallManyTimes(rest, func, args, index + 1); } } } Call it like … Read more
The Formula It’s actually very easy to compute N choose K without even computing factorials. We know that the formula for (N choose K) is: N! ——– (N-K)!K! Therefore, the formula for (N choose K+1) is: N! N! N! N! (N-K) —————- = ————— = ——————– = ——– x —– (N-(K+1))!(K+1)! (N-K-1)! (K+1)! (N-K)!/(N-K) K!(K+1) … Read more
You can first iterate through map entries and represent list elements as Map<String,Integer> and get a stream of lists of maps, and then reduce this stream to a single list. Try it online! Map<String, List<Integer>> mapOfLists = new LinkedHashMap<>(); mapOfLists.put(“a”, List.of(1, 2, 3)); mapOfLists.put(“b”, List.of(4, 5, 6)); mapOfLists.put(“c”, List.of(7)); List<Map<String, Integer>> listOfMaps = mapOfLists.entrySet().stream() // … 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
One of the best methods for calculating the binomial coefficient I have seen suggested is by Mark Dominus. It is much less likely to overflow with larger values for N and K than some other methods. public static long GetBinCoeff(long N, long K) { // This function gets the total number of unique combinations based … Read more
From Bit Twiddling Hacks Update Test program Live On Coliru #include <utility> #include <iostream> #include <bitset> using I = uint8_t; auto dump(I v) { return std::bitset<sizeof(I) * __CHAR_BIT__>(v); } I bit_twiddle_permute(I v) { I t = v | (v – 1); // t gets v’s least significant 0 bits set to 1 // Next set … Read more
Summary The full combinations of 4 to 9 distinctive numbers, minus the combinations which include invalid “jump”s. The Long Version The rule for Android 3×3 password grid: one point for once cannot “jump” over a point The author of the original post used Mathematica to generate all 985824 combinations. Because there is no “jump”, several … Read more