eigenclass - About problem formulations and ordered permutations

MAIN Index Search Changes PageRank Login

The mere formulation of a problem is far more essential than its solution, which may be merely a matter of mathematical or experimental skills. -- Albert Einstein

Here's an unremarkable example where the very description of the problem leads you in the wrong direction (on purpose?).

Here is an interesting coding challenge: write a counter function that counts from 1 to max but only returns numbers whose digits don’t repeat(...) Also display the biggest jump and the total count of numbers (...).

It suggests a brute-force solution, with max iterations and a predicate to verify if the counter satisfies the "no repeated digits criterion".

A vastly better approach (with 1126 times fewer iterations when considering numbers up to 10^10) becomes apparent if the problem is reworded as follows:

generate permutations of the digits '0' to '9' that do not start with '0' and whose numerical value is smaller than 'max', in increasing order

The "do not start with '0'" restriction is required to avoid generating a permutation twice (e.g. 12 and then 012), since a leading zero is ignored.

The easiest way to generate a permutation with m items from a set of n elements is to pick one element and prepend it to a (m-1) permutation of items from the resulting set of (n-1) elements. The "not starting with 0" criterion is fulfilled simply by picking the initial element from the digits different from zero and then putting zero back in the set used in the recursion.

Update (2008-07-10) A couple variants of the code below (still purely functional) which encode sets differently (using two lists, which won't surprise you at all if you've read Okasaki) are around 3 times faster and comparable in speed with Bob Lee's improved version.

This is expressed directly in OCaml as follows (you can find the full code of the OCaml and Ruby versions below):

module S = Set.Make(struct type t = int let compare = (-) end)
let (--) set elm = S.remove elm set

let permutations f zero digits len =
  let base = S.cardinal digits in
  let rec aux n digits = function
      0 -> f n
    | len -> S.iter (fun s -> aux (n * base + s) (digits -- s) (len-1)) digits
  in S.iter (fun s -> aux s (digits -- s) (len - 1)) (digits -- zero)

The function is general in the sense that it will find unique permutations in any base (that is, by placing the numbers 10 to 15 in the initial set, a sequence with the digits '0'..'9' + 'a'..'f' can be generated with the same code).

Here's the translation to Ruby:

def aux(n, len, syms, &b)
  if len == 0 
    yield n
    return
  end

  syms.each{|s| aux(n * 10 + s, len - 1, syms - [s], &b) }
end

def compute_seq(zero, syms, len, &b)
  (syms - [zero]).each{|s| aux(s, len - 1, syms - [s], &b) }
end

This version is not as general as the OCaml one, but that's not its only problem. This is how long it takes to find the 8877690 numbers under 10^10 with unique digits:

Ruby 1.8.6 (base 10)	73s
Ruby 1.9 (base 10)	63s
OCaml (any base)	0.640s

As usual, Ruby is 100 times slower.

The OCaml version is more general than the strict minimum required by the original problem (it works with arbitrary bases), and thus presumedly slower than a more specific one. It doesn't fare badly against the fastest implementation I've found, an equivalent solution in Java that uses a bitmask to represent the sets:

Java (base 10, bitset)

0.680s without JVM startup overhead

The Ruby solution uses Array#-, also know as "the poor man's set subtraction". Removing an element from an array is an O(n) operation. In the above-mentioned Java version, iterating over the remaining digits is O(all digits), instead of O(remaining ones). The OCaml version uses a set based on balanced trees where the relevant operations are logarithmic (it has a fairly large constant factor, so an integer set based on a bitset would be faster in this case). This means that the OCaml version would perform nearly as well with base-1000 permutations, as opposed to the other solutions which would become nearly 100 times slower.

Ironically, the OCaml stdlib is richer than Ruby's when it comes down to data structures. (The irony is that, while OCaml makes it very easy to build a data structure with good performance, in Ruby you are effectively stuck with the core classes implemented in C, which means essentially Array and Hash --- Ruby is so slow that algorithmic improvements hardly make up for the interpretation overhead.)

Here's the full code:

   (* Copyright (C) 2008 Mauricio Fernandez <mfp@acm.org> http//eigenclass.org
      Solution to the coding challenge at
      http://beust.com/weblog/archives/000491.html *)
   open Printf
   module S = Set.Make(struct type t = int let compare = (-) end)
   let (--) set elm = S.remove elm set
  
   let permutations f zero digits len =
     let base = S.cardinal digits in
     let rec aux n digits = function
         0 -> f n
       | len -> S.iter (fun s -> aux (n * base + s) (digits -- s) (len-1)) digits
     in S.iter (fun s -> aux s (digits -- s) (len - 1)) (digits -- zero)
 
   let () =
     let max = 10_000_000_000 in
     let digits = List.fold_right S.add [0; 1; 2; 3; 4; 5; 6; 7; 8; 9] S.empty in
  
     let count = ref 0 and prev = ref 0 and maxj = ref 0 and base = ref 0 in
     let report () = printf "Found %d numbers under %d.\n" !count max;
                     printf "Max jump: %d (%d -- %d).\n" !maxj !base (!base + !maxj)
   
     in try
       for i = 1 to 10 do
         permutations
           (fun num ->
              if num >= max then raise Exit;
              (* printf "%d\n" num; *)
              incr count;
              let jump = num - !prev in
                if jump > !maxj then (maxj := jump; base := !prev);
                prev := num)
           0 digits i
       done;
       report ()
     with Exit -> report ()

# Copyright (C) 2008 Mauricio Fernandez <mfp@acm.org> http//eigenclass.org
# Solution to the coding challenge at
# http://beust.com/weblog/archives/000491.html

def aux(n, len, syms, &b)
  if len == 0 
    yield n
    return
  end

  syms.each{|s| aux(n * 10 + s, len - 1, syms - [s], &b) }
end

def compute_seq(zero, syms, len, &b)
  (syms - [zero]).each{|s| aux(s, len - 1, syms - [s], &b) }
end

max = 10_000_000_000
digits = (0..9).to_a

count = prev = maxj = base = 0

(1..10).each do |i|
  compute_seq(0, digits, i) do |x|
    break if x >= max 
    # puts x
    count += 1
    j = x - prev
    maxj, base = j, prev if j > maxj 
    prev = x
  end
end

puts "Found #{count} numbers under #{max}."
puts "Max jump: #{maxj} (#{base} -- #{base + maxj})."

No Title - Anonymous (2008-07-02 (Wed) 13:17:40)

I'd rephrase "permutations of the digits '0' to '9'" as "permutations from the digits ..." or "permutations of a subset of the digits...". I'm not sure about the former of the proposed; I don't know if "permutations from ..." has a well defined mathematical meaning. But I do know that the original (in my interpretation) would require each of the digits to be used.

Jacob Fugal 2008-07-02 (Wed) 13:22:26

Sorry, that above comment was from me. You can also disregard it. From http://en.wikipedia.org/wiki/Permutation:

In combinatorics, a permutation is usually understood to be a sequence containing each element from a finite set once, and only once...

However, there is also a traditional more general meaning of the term "permutation" used in combinatorics. In this more general sense, permutations are those sequences in which, as before, each element occurs at most once, but not all elements of the given set need to be used.

I was only familiar with the first definition; you are obviously using the second.

mfp 2008-07-02 (Wed) 13:29:42

I hesitated as I was writing it. I actually thought I was abusing the language since I was only familiar with the first definition :-), but "sequences with m elements taken from the original set where none is repeated" (the expression that came to mind) weighs a billion tons.

hmm I still suspect it's a convenient abuse of language.