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

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).

## 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). • Fastest-algorithm doesn't work for this. With an upper limit on the input, all solutions are automatically O(1). – Dennis Nov 3 '18 at 21:22 • Fastest-code works then. Make sure to include your machine's specs (hardware and OS) in the challenge, so people can tune for it. – Dennis Nov 3 '18 at 21:36 • How about giving this a less clumsy title like "find all permutations of the input" with "- distinct values guaranteed" – Titus Nov 4 '18 at 10:35 • You shouldn't use any shared computer for timing code; TIO is no exception. Your best bet is to run the code on your own machine. – Dennis Nov 4 '18 at 15:41 • While it may be "hard to tell exactly what you're asking" according to the reason cited for close votes for several users, it is impossible to "clarify your specific problem or add additional details to highlight exactly what you need" where those users who have voted to close the question citing "unclear what you're asking" have made absolutely no attempt to clarify what is not clear to them at the question. – guest271314 Nov 8 '18 at 15:28 ## 5 Answers # 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) • Can you explain the algorithm. Is the time referenced at the answer the result at linked tio, or was another method used to measure time to complete the task? – guest271314 Nov 4 '18 at 14:37 • Can you explain the algorithm? $ time runhaskell f.hs >> output real 0m30.826s user 0m17.053s sys 0m13.613s – guest271314 Nov 4 '18 at 17:10
• Is runghc installed when haskell-platform is installed? \$ dpkg --get-selections | grep runghc does not output any result – guest271314 Nov 4 '18 at 17:15
• @guest271314 I added an explanation. I do not recall installing runghc independently, so it should be part of the Haskell platform. – Laikoni Nov 4 '18 at 17:35
• @guest271314 Also the timing is actually faster if you compile first and then run the program, e.g. ghc --make -O2 code.hs. Then the last testcase runs in ~ 1.3 seconds on my machine. – Laikoni Nov 4 '18 at 17:37

# 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.

• Can you explain the algorithm? – guest271314 Nov 7 '18 at 1:26
• First call at console using .time() and .timeEnd() was 133.01708984375ms or 0.133017089843749992 seconds; second call 223.14404296875ms, third call 199.989013671875ms. – guest271314 Nov 7 '18 at 1:54
• Hi @guest271314. I added an explanation. Hope it helps!. – wolfhammer Nov 7 '18 at 3:38

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

• Can you explain the algorithm? – guest271314 Nov 5 '18 at 2:14
• How to get the CL-USER> prompt? Installed sbcl and ran the program which printed to STDOUT though time was not printed. – guest271314 Nov 10 '18 at 16:49

## 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 = 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.

• Is the output intended to be 30.9692 instead of "The only valid output is an array (set; list) of length equal to the factorial of input" at linked tio? – guest271314 Nov 22 '18 at 17:37
• Have not run *indows in quite some time. How to install .NET version of C# at *nix to test? – guest271314 Nov 22 '18 at 17:42
• That's the output of the timing framework. The array is the return value of the method Foo. For Linux your choices are Mono and .Net Core. Don't know what options there are for BSD. – Peter Taylor Nov 22 '18 at 17:59
• The expected output is the array of integers. Will attempt to install Mono and test the code. Compilation instructions? – guest271314 Nov 22 '18 at 18:17
• mono-csc Foo.cs will produce Foo.exe which I think can run as ./Foo.exe and if not can run as mono Foo.exe – Peter Taylor Nov 22 '18 at 18:24

# 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)
{
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;
unsigned long index = 0;
if (!bsr(&index, _mm_extract_epi64(mask, 0))) k = size - 1;
else k = index / 8;
}
else k = (index / 8) + 8;

uint8_t l = 8;
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