Given a number n, list all n-digit numbers such that each number does not have repeating digits

I'm trying to solve the following problem. Given an integer, n, list all n-digits numbers such that each number does not have repeating digits.

For example, if n is 4, then the output is as follows:

My present approach is by brute-force. I can generate all n-digit numbers, then, using a Set, list all numbers with no repeating digits. However, I'm pretty sure there is a faster, better and more elegant way of doing this.

I'm programming in Java, but I can read source code in C.

Thanks

4 Answers
4

Mathematically, you have 10 options for the first number, 9 for the second, 8 for the 3rd, and 7 for the 4th. So, 10 * 9 * 8 * 7 = 5040.

Programmatically, you can generate these with some combinations logic. Using a functional approach usually keeps code cleaner; meaning build up a new string recursively as opposed to trying to use a StringBuilder or array to keep modifying your existing string.

Example Code

The following code will generate the permutations, without reusing digits, without any extra set or map/etc.

public class LockerNumberNoRepeats
public static void main(String args)
System.out.println("Total combinations = " + permutations(4));


public static int permutations(int targetLength)
return permutations("", "0123456789", targetLength);


private static int permutations(String c, String r, int targetLength)
if (c.length() == targetLength)
System.out.println(c);
return 1;


int sum = 0;
for (int i = 0; i < r.length(); ++i)
sum += permutations(c + r.charAt(i), r.substring(0,i) + r.substring(i + 1), targetLength);

return sum;




Output:

...
9875
9876
Total combinations = 5040


Explanation

Pulling this from a comment by @Rick as it was very well said and helps to clarify the solution.

So to explain what is happening here - it's recursing a function which takes three parameters: a list of digits we've already used (the string we're building - c), a list of digits we haven't used yet (the string r) and the target depth or length. Then when a digit is used, it is added to c and removed from r for subsequent recursive calls, so you don't need to check if it is already used, because you only pass in those which haven't already been used.

it's easy to find a formula. i.e.

if n=1 there are 10 variants.

n=1

10

if n=2 there are 9*10 variants.

n=2

9*10

if n=3 there are 8*9*10 variants.

n=3

8*9*10

if n=4 there are 7*8*9*10 variants.

n=4

7*8*9*10

Note the symmetry here:

0123
0124
...
9875
9876


9876 = 9999 - 123

9875 = 9999 - 124

So for starters you can chop the work in half.

It's possible that you might be able to find a regex which covers scenarios such that if a digit occurs twice in the same string then it matches/fails.

Whether the regex will be faster or not, who knows?

Specifically for four digits you could have nested For loops:

for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
if (j != i) {
for (int k = 0; k < 10; k++) {
if ((k != j) && (k != i)) {
for (int m = 0; m < 10; m++) {
if ((m != k) && (m != j) && (m != i)) {
someStringCollection.add((((("" + i) + j) + k) + m));


(etc)

Alternatively, for a more generalised solution, this is a good example of the handy-dandy nature of recursion. E.g. you have a function which takes the list of previous digits, and required depth, and if the number of required digits is less than the depth just have a loop of ten iterations (through each value for the digit you're adding), if the digit doesn't exist in the list already then add it to the list and recurse. If you're at the correct depth just concatenate all the digits in the list and add it to the collection of valid strings you have.

Backtracking method is also a brute-force method.

private static int pickAndSet(byte used, int last)
if (last >= 0) used[last] = 0;
int start = (last < 0) ? 0 : last + 1;
for (int i = start; i < used.length; i++)
if (used[i] == 0)
used[i] = 1;
return i;


return -1;


public static int get_series(int n)
if (n < 1


Required, but never shown

Required, but never shown

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.