Fastest algorithm to output array containing all integers in range excluding duplicate digits

Question

Input is a single integer in ascending digit order.

The only valid inputs are:

12
123
1234
12345
123456
1234567
12345678
123456789

The only valid output is an array (set; list) of length equal to the factorial of input:

Input - Factorial of input - Output array length

12 -> 1*2 -> 2
123 -> 1*2*3 -> 6
1234 -> 1*2*3*4 -> 24
12345 -> 1*2*3*4*5 -> 120
123456 -> 1*2*3*4*5*6 -> 720
1234567 -> 1*2*3*4*5*6*7 -> 5040
12345678 -> 1*2*3*4*5*6*7*8 -> 40320
123456789 -> 1*2*3*4*5*6*7*8*9 -> 362880

The output array is all integers of input length in lexicographical order.

For example, given input 123 -> factorial of input is 1*2*3=6 -> for each of the six array elements output the input integer and the five remaining integers of the array in lexicographic order -> [123,132,213,231,312,321]. Notice that the last element is always the input integer in reverse order.

Test Cases

Input  Output
`12` ->  `[12,21]` // valid output, ascending numeric order
`12` ->  `[12.0,21.0]` // invalid output, output must be rounded to integer
`123` -> `[123,132,213,231,312,321]` // valid output
`123` -> `[123,132,213,222,231,312,321]` // invalid output: `222` are duplicate digits
`123` -> `[123,142,213,231,213,321]` // invalid output: `142` outside range `1-3`
`123456789` -> `[987654321,...,123456789]` // valid output, descending numeric order
`123456789` -> `[987654321,...,123456798]` // invalid output, `123456798` is greater than the minimum required integer in resulting array `123456789`

Rules

• Do not use standard library functions for permutations or combinatorics.
• If the algorithm produces an integer greater or less than input minimum or maximum only the integers in the specified range must be output. (Technically, if input is 12345 we could generate all integers to 21 or 12, though for input 12345 the only valid output must be within the range 12345 through 54321).
• Output must be an array (set; list) of integers, not strings.
• The integers output must not be hardcoded.
• The output integers must not include duplicate digits (more than one of the same digit at that array index).

Winning criteria

fastest-code

Hardware, OS

Where submissions will be run

~$ lscpu
Architecture:          i686
CPU op-mode(s):        32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                2
On-line CPU(s) list:   0,1
Thread(s) per core:    1
Core(s) per socket:    2
Socket(s):             1
Vendor ID:             GenuineIntel
CPU family:            6
Model:                 37
Model name:            Intel(R) Pentium(R) CPU        P6200  @ 2.13GHz
Stepping:              5
CPU MHz:               2133.000
CPU max MHz:           2133.0000
CPU min MHz:           933.0000
BogoMIPS:              4256.26
L1d cache:             32K
L1i cache:             32K
L2 cache:              256K
L3 cache:              3072K

~$ free -m
              total        used        free      shared  buff/cache   available
Mem:           3769        1193         802         961        1772        1219
Swap:             0           0           0

~$ uname -r
4.8.0-36-lowlatency

Kindly explain the algorithm within the body of the answer.

For languages used other than JavaScript (which will test at Chromium 70) will take the time to install the language and test the code for the time taken to output the requirement, as there is no way (that have found) to provide uniform results as to time for every possible language used to derive output (see this comment).

Answer 1

Haskell, 6.9 s

f [] [x] = [[x]]
f [] [x,y] = [[x,y],[y,x]]
f l (x:r) = map (x:) (f [] $ l++r) ++ f (l++[x]) r
f _ [] = []

g :: Int -> [Int]
g = map read . f [] . show

Try it online! g is the main function which converts the input to a string and the result to a list of integers. f recursively performs the shuffling.

The algorithm works as follows: Given 123, we need to generate [123,132,213,231,312,321]. This can be done in parts by taking the first digit 1, recursively computing the list for the remaining digits 23 -> [23,32] and adding 1 to the front again: [123,132]. Then we do the same with 2 and the remaining digits 13 to get [213,231] and with 3 and 12 to get [312,321]. Finally, the three lists are concatenated.

This works in the same way for larger numbers. f handles two lists, the first one (l) contains all digits left from the current digit, the second one (x:r) has the current digit x at the first position, followed by the remaining digits r. We recursively call f with all but the current digit (that is l and r concatenated) (f [] $ l++r) and add the current digit x to the front of each element in the resulting list: map (x:). We then finished processing x and add it to the end of the l list and recursively call f (l++[x]) r to handle the next digit.

---

The largest test case g 123456789 takes ~6.9s on OPs machine:

real 0m6.877s user 0m4.439s sys 0m0.056s

(~0.1s on my own machine)

Answer 2

JavaScript 0.185 Seconds

function fact(x) {

  x+=""
  var rL=1,rI=0,i=0
  if(x.length <2)return [x]
  for(i;i<x.length;i++)rL*=(i+1);
  var r = new Array(rL);
  function loop(p, s) {
    var l = s.length, i=0;
    if (l === 2) {
      r[rI++] = (p + s)*1;
      r[rI++] = (p + s.charAt(1) + s.charAt(0)) * 1;
      return;
    }
    while (i < l) {
      loop(p + s.charAt(i), s.substr(0,i) + s.substr(++i));
    }
  }
  loop("",x)
  return r;
}

This function creates an array r of length "factorial of input length". It then has a recursive loop of with parameters for prefix and suffix (p and s). It starts the loop with an empty prefix and a suffix of the input. It then checks the base case of suffix length equal to 2 and if reached adds those results. If it's not a base case then loop through the suffix characters, take a character at index and add it to prefix, remove that character from the suffix, and loops those as a new prefix and suffix. This will continue until input length factorial results are added to array r.

Answer 3

Common Lisp SBCL 0.157 seconds

(defun num-permutations (list)
  (cond ((null list) nil)
        ((null (cdr list)) (list list))
        (t (loop for element in list
             append (mapcar (lambda (l) (cons element l))
                            (num-permutations (remove element list)))))))

here is the run with 1-9

CL-USER> (time (num-permutations '(1 2 3 4 5 6 7 8 9)))
Evaluation took:
  0.157 seconds of real time
  0.156455 seconds of total run time (0.140332 user, 0.016123 system)
  [ Run times consist of 0.081 seconds GC time, and 0.076 seconds non-GC time. ]
  99.36% CPU
  468,738,490 processor cycles
  165,083,680 bytes consed

Answer 4

C# (31 ms)

    static int[] Foo(int perm) {
        int n = perm.ToString().Length, fact = n;
        int[] pow10 = new int[n];
        pow10[n - 1] = 1;
        for (int k = n - 2; k >= 0; k--) {
            pow10[k] = 10 * pow10[k + 1];
            fact *= k + 1;
        }

        int[] rv = new int[fact];
        rv[0] = perm;
        int z = 1, i = n - 1, pi = perm/pow10[i]%10;
        while (true) {
            int pidec = perm/pow10[i-1]%10;
            if (pidec > pi) {
                if (--i == 0) return rv;
                pi = pidec;
            }
            else {
                int j = n - 1;
                while (perm/pow10[j]%10 < pidec) j--;

                perm += (perm/pow10[i-1]%10 - perm/pow10[j]%10) * (pow10[j] - pow10[i-1]);
                for (j = n - 1; i < j; i++, j--)
                    perm += (perm/pow10[i]%10 - perm/pow10[j]%10) * (pow10[j] - pow10[i]);

                rv[z++] = perm;
                i = n - 1;
                pi = perm/pow10[i]%10;
            }
        }
    }

Online demo

The algorithm is the standard one.

Answer 5

C++

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <chrono>
#include <cstring>

#include <emmintrin.h>
#include <smmintrin.h>

unsigned char bsr(unsigned long* index, unsigned long long mask)
{
    if (!mask) return 0;
    *index = 63 - __builtin_clzll(mask);
    return 1;
}

std::vector<uint32_t> findPermulations(uint32_t input)
{
    std::string tmp = std::to_string(input);
    size_t size = std::distance(tmp.begin(), tmp.end());
    uint8_t* perm = (uint8_t*)_mm_malloc(32, 64);
    memcpy(perm, tmp.data(), size);
    memset(perm + size, 0, 64 - size);
    for (size_t i = 0; i < size; i++) {
        perm[i] -= '0'; // Convert char to uint8_t
    }


    size_t fact = 1;
    for (size_t i = 0; i < size; i++) {
        fact *= perm[i];
    }

    std::vector<uint32_t> results;
    results.reserve(fact);
    results.push_back(input);

    for (size_t i = 1; i < fact; i++)
    {
        uint8_t k;
        __m128i mask = _mm_cmplt_epi8(_mm_load_si128((__m128i*)perm), _mm_loadu_si128((__m128i*)(perm + 1)));
        unsigned long index = 0;
        if (!bsr(&index, _mm_extract_epi64(mask, 1))) {
            if (!bsr(&index, _mm_extract_epi64(mask, 0))) k = size - 1;
            else k = index / 8;
        }
        else k = (index / 8) + 8;

        uint8_t l = 8;
        mask = _mm_cmplt_epi8(_mm_set1_epi8(perm[k]), _mm_load_si128((__m128i*)perm));
        if (!bsr(&index, _mm_extract_epi64(mask, 1))) {
            bsr(&index, _mm_extract_epi64(mask, 0));
            l = 0;
        }

        l += index / 8;

        std::swap(perm[k], perm[l]);
        std::reverse(perm + k + 1, perm + size);

        uint32_t result = 0;
        for (size_t i = 0; i < size; i++) {
            result *= 10;
            result += perm[i];
        }

        results.push_back(result);
    }
    _mm_free(perm);
    return results;
}

int main()
{
    std::cout << "Press any key to begin...\n";
    std::cin.get();
    auto start = std::chrono::high_resolution_clock::now();
    auto perms = findPermulations(123456789);
    auto end = std::chrono::high_resolution_clock::now();
    std::cout << "Completed in " << std::chrono::duration<double, std::milli>(end - start).count() << "ms\n";
    return 0;
}   

Regular algorithm. If std::reverse count counts as a library permutation function, replace with:

void reverse(uint8_t* first, uint8_t* last){
    while ((first != last) && (first != --last)) {
        std::iter_swap(first++, last);
    }
}

Swaps don't really count as permutations, put you could change them anyway.

Compile with clang 6.0: clang++-6.0 find.cpp -O3 -mssse3 ./a.out