CODEWITHSUNDEEP
c#algorithm
else forty
else forty

Reputation: 73

Count of all possible numbers constructed from given set of digits up to given length

I'm trying to generate all possible numbers from an int array representing digits for the number.

for an example arr= new int[]{1,2} I get the following.

1
2
11
21
12
22

count =6.

for an example arr= new int[]{1,2,3} i get the following.

1 2 3 11 21 31 12 22 32 13 23 33 111 211 311 121 221 321 131 231 331 112 212 312 122 222 322 132 232 332 113 213 313 123 223 323 133 233 333

count =39.

I'm not really sure if this is the correct number of entries i should be getting specially for bigger size input arrays.

Is there any math formula for this that I'm not aware of? I know n! does not apply for this case.

Here is the code that I wrote to calculate all possible combinations

class HelloWorld {
static void Main() {
    var output =  GenerateAllCombinations(new int[] {1,2,3});
    foreach(var o in output )
    {
     Console.WriteLine(o);
    }
     Console.WriteLine(output.Count);
}

public static HashSet<string> GenerateAllCombinations(int[]  nums){
    //convert int array to string array
    var strNums=nums.Select(x =>x.ToString()).ToArray();

    var cach = new HashSet<string>(strNums);       
    var output = new HashSet<string>(strNums);

       for(int u=1;u<strNums.Length;u++)
     {
            var temp = new HashSet<string>(); 
         for(int i=0;i<strNums.Length;i++)
         {
                 foreach(var h  in cach )
                 {
                     temp.Add(h+strNums[i]);
                 }
         }
         cach=new HashSet<string>(temp);
         output.UnionWith(temp);
       }
         
    return output;
 }
}

Upvotes: 1

Views: 467

Answers (1)

Abhinav Mathur
Abhinav Mathur

Reputation: 8101

For n distinct digits,

  1. Count of single digit numbers = n
  2. Count of 2 digit numbers = n^2
  3. Count of 3 digit numbers = n^3
  4. Count of n digit numbers = n^n

Total distinct numbers = n + n^2 + n^3 … + n^n = n * ((n^n) - 1) / (n-1) (using the simple geometric progression summation.

Edit: As per @AlexeiLevenkov's suggestion, if 0 is included in the digits, there are two cases:

  1. If sequence evaluation is done as strings, the answer stays the same
  2. If sequence evaluation is done as numbers, the answer becomes n^n

Upvotes: 3

Related Questions