permutations of certain digits in Java

Question

I realize permutations in programming language is a very frequently asked question, however I feel like my question is sort of unique.

I have received input of a certain length integer N and stored each digit in an array where the index of the array stores the number of times that digit occurs in N.

now I want to test if some function holds true with all permutations of N's original length with no leading zeroes. Ex:

int[] digits = new int[10];
String n = "12345675533789025";
for (char c : n.toCharArray())
    digits[c-'0']++;
for (Long f : allPermutationsOf(digits))
    if (someCondition(f))
        System.out.println(f);

a precondition to the following code is that N must be less than 2^64-1, (long's maximum value.)

The question is, how would I take all permutations of the digits array and return a Long[] or long[] without using some kind of String concatenation? Is there a way to return a long[] with all permutations of digits[] in the "Integer scope of things" or rather using only integer arithmetic?

Answer 1

To elaborate on one of the above comments, putting a digit d in a given place in the resulting long is easy: d*1 puts it in the 1s place, d*1000 puts it in the thousands place, and in general d * (10^k) puts d into the k+1th digit. You have N total digits to fill, so you need to do permutations on the powers of 10 from 1 to 10^(N-1).

Answer 2

If you are expecting the permutations to be Longs anyway, instead of representing n as an array of counts, it might be easier to represent it as a Long too.

Here are a couple of ways you can generate the permutations.

1. Think of generating permutations as finding the next largest number with the same set of digits, starting from the number consisting of the sorted digits of n. In this case, the answers to this StackOverflow question is helpful. You can use arithmetic operations and modding instead of string concatenation to implement the algorithm there (I can provide more details if you like). A benefit of this is that the permutations you generate will automatically be in order.

2. If you don't care about the order of the permutations and you expect the number of digit duplicates to be small, you can use the Steinhaus-Johnson-Trotter algorithm, which (according to Robert Sedgewick) is the fastest algorithm for generating permutations of unique elements. To make sure duplicate permutations are not generated, you would have to distinguish every duplicate digit and only emit the permutations where they appear in order (i.e., if 2 appears three times, then create the elements 2_1, 2_2, 2_3 and make sure those three elements always appear in that order in an emitted permutation).

Answer 3

For the requirement, assuming that the length of N is n, we can generate all permutations by going from digit to digit, starting from 0 and end at n - 1. With 0 is the leading digit.

For each digit, we only go through each possibility (0 to 9) once , which will avoid duplicate permutation.

From digit x to digit x + 1, we can easily generate the current value by passing a number called current

For example: at digit 3, we have current = 1234, so at digit 4, if we choose 5 to be at digit 4, the current will be 1234*10 + 5 = 12345

Sample code in Java:

public void generate(int index, int length, int[] digits, long current, ArrayList<Long> result) {
    //All the permutation will be stored in result ArrayList
    for (int i = 0; i < 10; i++) {
        if (digits[i] > 0 && (i != 0 || index != 0)) {                
            digits[i]--;
            if (index + 1 == length) {//If this is the last digit, add its value into result
                result.add(current * 10 + i);
            } else {//else, go to next digit
                generate(index + 1, length, digits, current * 10 + i, result);
            }
            digits[i]++;
        }
    }
}