Project Euler Problem 24

Problem 24

16 August 2002

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

012   021   102   120   201   210

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

Answer: 2783915460

 

 

C#

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1 {
    class Program {
        const int stopAt = 1000000;
        static int count = 0;
        static void permuteHelper(int[] n, int level) {
            if (level > n.Length - 1) {
                count++;
                //Console.Write(count + ": ");
                //foreach (var x in n) Console.Write(x);
                //Console.WriteLine();
                //Console.ReadKey();
                if (count >= stopAt) {
                    foreach (var x in n) Console.Write(x);
                    Console.ReadKey();
                    Environment.Exit(0);
                }
                return;
            }
            for (int i = 0; i <= 9; i++) {
                bool hasDuplicate = false;
                for (int priorLevel = 0; priorLevel < level; priorLevel++) {
                    if (i == n[priorLevel]) {
                        hasDuplicate = true;
                        break;
                    }
                }
                if (!hasDuplicate) {
                    n[level] = i;
                    permuteHelper(n, level + 1);
                }
            }
        }

        static void permute(int[] n) {
            permuteHelper(n, 0);
        }

        static void Main(string[] args) {
            int[] num = new int[10];
            foreach(var x in num) Console.Write(" " + x);
            Console.WriteLine();

            permute(num);
        }
    }
}

Racket

(require racket/generator)
(define (permute v)
  (generator ()
             (define count 0)
             (define len (vector-length v))
             (define sorted (sort (vector->list v) <))
             (let loop ([level 0])
               (if (> level (sub1 len))
                   (begin
                     (set! count (add1 count))
                     (yield v))
                   (for ([i sorted])
                     (unless (for/or ([priorLevel (in-range 0 level)])
                               (= i (vector-ref v priorLevel)))
                       (vector-set! v level i)
                       (loop (add1 level))))))))

(define p (permute (list->vector (range 0 10))))
(let loop ([count 1])
  (when (<= count 1000000)
    (define v (p))
    (if (= count 1000000)
        (displayln v)
        (loop (add1 count)))))