This is along the lines of Thijser’s currently incomplete pseudocode. The idea is to take the most frequent of the remaining item types unless it was just taken. (See also Coady’s implementation of this algorithm.) import collections import heapq class Sentinel: pass def david_eisenstat(lst): counts = collections.Counter(lst) heap = [(-count, key) for key, count in … Read more
I assume you’re asking about combinations in combinatorial sense (that is, order of elements doesn’t matter, so [1 2 3] is the same as [2 1 3]). The idea is pretty simple then, if you understand induction / recursion: to get all K-element combinations, you first pick initial element of a combination out of existing … Read more
To describe a permutation of n elements, you see that for the position that the first element ends up at, you have n possibilities, so you can describe this with a number between 0 and n-1. For the position that the next element ends up at, you have n-1 remaining possibilities, so you can describe … Read more
Sure thing. It is a bit tricky to do this with LINQ but certainly possible using only the standard query operators. UPDATE: This is the subject of my blog on Monday June 28th 2010; thanks for the great question. Also, a commenter on my blog noted that there is an even more elegant query than … Read more
This is very easy with list comprehensions. To get the cartesian product of the lists xs and ys, we just need to take the tuple (x,y) for each element x in xs and each element y in ys. This gives us the following list comprehension: cartProd xs ys = [(x,y) | x <- xs, y … Read more
function pc_permute($items, $perms = array()) { if (empty($items)) { echo join(‘ ‘, $perms) . “<br />”; } else { for ($i = count($items) – 1; $i >= 0; –$i) { $newitems = $items; $newperms = $perms; list($foo) = array_splice($newitems, $i, 1); array_unshift($newperms, $foo); pc_permute($newitems, $newperms); } } } $arr = array(‘peter’, ‘paul’, ‘mary’); pc_permute($arr); or … Read more
You are looking for the Cartesian Product. In mathematics, a Cartesian product (or product set) is the direct product of two sets. In your case, this would be {1, 2, 3, 4, 5, 6} x {1, 2, 3, 4, 5, 6}. itertools can help you there: import itertools x = [1, 2, 3, 4, 5, … Read more
Since this nice question has been brought back to life, here’s a fresh answer. The problem is solved recursively: If you already have a partition of n-1 elements, how do you use it to partition n elements? Either place the n‘th element in one of the existing subsets, or add it as a new, singleton … Read more
You’re looking for the permutations formula: nPk = n!/(n-k)! In your case, you have 9 entries and you want to choose all of them, that’s 9P9 = 9! = 362880 You can find a PHP algorithm to permutate in recipe 4.26 of O’Reilly’s “PHP Cookbook”. pc_permute(array(0, 1, 2, 3, 4, 5, 7, 8)); Copied in … Read more
Consider this solution using the NDGRID function: sets = {[1 2], [1 2], [4 5]}; [x y z] = ndgrid(sets{:}); cartProd = [x(:) y(:) z(:)]; cartProd = 1 1 4 2 1 4 1 2 4 2 2 4 1 1 5 2 1 5 1 2 5 2 2 5 Or if you want … Read more