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

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





Can you tell what exactly brute force method you are trying? It would be better if you include your generating combination routine (function or method )
– Brij Raj Kishore
Aug 30 at 0:57






It looks like a simple exercise. The guys here are too kind to give you their solutions. I would recommend you to give out your attempt (code) and ask about where you stuck, what is wrong, or why is it not efficient enough, etc...
– Nin
Aug 30 at 1:24





@Nin totally agree with you. But before explaining the problem here the guys have already given her straightforward answer. A simple google search and geeksforgeeks would do the same
– Brij Raj Kishore
Aug 30 at 1:30






@Maribell, can we avoid leading zero?
– The Scientific Method
Aug 30 at 2:35





You may want to clarify whether you want all numbers up to n digits or just n digits. You used 0123 in your example, which is n-1 digits in your n=4 example. This changes the acceptable answer to a sequence like 9*9*8*7...
– technosaurus
Aug 30 at 14:01




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.





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. Nice finesse.
– Rick
Aug 30 at 1:33






@John Many thanks, this works as a charm and is much faster than my brute-force approach.
– Maribell Pina Griego
Aug 30 at 5:11





@Rick - Awesome explanation. I meant to go back and add one in the morning. I'll include it in the solution with your name.
– John Humphreys - w00te
Aug 30 at 12:58





@MaribellPinaGriego - No problem at all. FYI, there is probably an iterative approach to this using a stack + while loop that would be even faster with basically the same logic. Recursive solutions are usually the simplest to understand and the least code but they are rarely the fastest as all the nested function calls are not optimal.
– John Humphreys - w00te
Aug 30 at 13:03





Technically he has 9 options for the first number since a 0 would make it a n-1 digit number. But the question makes that confusing.
– technosaurus
Aug 30 at 14:03



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.

Popular posts from this blog

𛂒𛀶,𛀽𛀑𛂀𛃧𛂓𛀙𛃆𛃑𛃷𛂟𛁡𛀢𛀟𛁤𛂽𛁕𛁪𛂟𛂯,𛁞𛂧𛀴𛁄𛁠𛁼𛂿𛀤 𛂘,𛁺𛂾𛃭𛃭𛃵𛀺,𛂣𛃍𛂖𛃶 𛀸𛃀𛂖𛁶𛁏𛁚 𛂢𛂞 𛁰𛂆𛀔,𛁸𛀽𛁓𛃋𛂇𛃧𛀧𛃣𛂐𛃇,𛂂𛃻𛃲𛁬𛃞𛀧𛃃𛀅 𛂭𛁠𛁡𛃇𛀷𛃓𛁥,𛁙𛁘𛁞𛃸𛁸𛃣𛁜,𛂛,𛃿,𛁯𛂘𛂌𛃛𛁱𛃌𛂈𛂇 𛁊𛃲,𛀕𛃴𛀜 𛀶𛂆𛀶𛃟𛂉𛀣,𛂐𛁞𛁾 𛁷𛂑𛁳𛂯𛀬𛃅,𛃶𛁼

Crossroads (UK TV series)

ữḛḳṊẴ ẋ,Ẩṙ,ỹḛẪẠứụỿṞṦ,Ṉẍừ,ứ Ị,Ḵ,ṏ ṇỪḎḰṰọửḊ ṾḨḮữẑỶṑỗḮṣṉẃ Ữẩụ,ṓ,ḹẕḪḫỞṿḭ ỒṱṨẁṋṜ ḅẈ ṉ ứṀḱṑỒḵ,ḏ,ḊḖỹẊ Ẻḷổ,ṥ ẔḲẪụḣể Ṱ ḭỏựẶ Ồ Ṩ,ẂḿṡḾồ ỗṗṡịṞẤḵṽẃ ṸḒẄẘ,ủẞẵṦṟầṓế