Combinatorics with repeated chars on initial group

Question

I know that if I have the following group of numbers

{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }

I can have 5040 different 4-digit numbers, using 10! / (10 - 4)!

But if I repeat one number on the initial group, like

{ 1, 1, 2, 3, 4, 5, 6, 7, 8, 9 }

How many different 4-digit numbers can we build ? I know the answer is 3360, just don't know how to implement it.

Important: In this case, numbers like "1123" or "1213" should be valid combinations, but not "1113", as there are only two ones on the initial group.

Also, for the group

{ 1, 1, 2, 2, 3, 4, 5, 6, 7, 8 }

There should be 2190 4-digit numbers. Any ideas on how to calculate these answers ?

This is not homework, I'll get this numbers from a specific hardware and depending on the number of combinations, will return some data.

Answer 1

{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }

Here you are choosing four numbers from ten and they can be any order. Thus the solution is

(10 choose 4) * 4! = 5040.

Now we consider the case of

{ 1, 1, 2, 3, 4, 5, 6, 7, 8, 9 }

There are a few combinations here. We can have zero 1s, one 1 or two 1s. In the first case there are

(8 choose 4) * 4!

possible combinations. In the second case there are

(8 choose 3) * 4!

possible combinations. In the third case there are

(8 choose 2) * 4! / 2!

possible combinations. This last one requires explanation. There are eight possible non 1 digits to choose from and we are choosing two. The two remaining digits are 1s (by assumption that we are in the case where are our 4-string contains two 1s). We can put these four digits in any order however the 1s are interchangeable so we divide by the number of possible orderings of the 1s (2!).

Thus the answer is

(8 choose 4) * 4! + (8 choose 3) * 4! + (8 choose 2) * 4! / 2! = 3360.

For the case of

{ 1, 1, 2, 2, 3, 4, 5, 6, 7, 8 }

there are again a few combinations. We can have zero 1s and zero 2s, one 1 and zero 2s, two 1s and zero 2s, two 1s and one 2, two 1s and two 2s, zero 1s and one 2, zero 1s and two 2s, one 1 and two 2s, and one 1 and one 2. These can be worked out as above and the final answer is

(6 choose 4) * 4!
    + 2 * (6 choose 3) * 4!
    + 2 * (6 choose 2) * 4! / 2!
    + (6 choose 2) * 4!
    + 2 * (6 choose 1) * 4! / 2!
    + (6 choose 0) * 4! / (2! * 2!)
= 2190.

This a fairly simplistic approach to problems of this sort. There are others (for example, inclusion/exclusion) that are more sophisticated but the current approach is the easiest to understand if you're seeing problems of this sort for the first time.

Answer 2

You might want to reference this outstanding Combinatorics implementation.

Answer 3

This would be pretty easy without duplication . . . for

{ 1, 1, 2, 3, 4, 5, 6, 7, 8, 9 }

Since you only have 9 distinct choices (as opposed to the 10 in the original problem), the answer should be 9! / (9 - 4)!

( By the way, you can actually have more different 4-digit numbers if you allow repetition, i.e. 4456. Then the answer would just be 9^4 4-digit numbers. )

Similarly, {1, 1, 2, 2, 3, 4, 5, 6, 7, 8 } has 8 distinct choices, so the answer should be 8! / (8 - 4)! by your original math.

Edit and actual answer: Maybe you meant that if the 1 is duplicated in your set, you can use two 1's in the answer?

Edit 2: Working, tested python module provided

In that case, you might try calculating the distinct number of possibilities, and then adding the results with duplicates, as the following python code suggests):

import math

def set_exclude(a, b):
    result = []
    for i in a:
        if not i in b:
            result.append(i)
    return result

def cnt_unique(aset, choices_picked, count_left, count_total):
    # Sanity check
    if count_left < 0:
        return 0
    if count_left == 0:
        return math.factorial(count_total)
    # Do non-duplicate combinations first
    # Set unprocessed = (set without any elements in choices_picked)
    unprocessed = set_exclude(aset, choices_picked)
    temp = len(set(unprocessed))

    # If we have no more valid items to choose from, this is impossible
    if temp >= count_left:
        result = math.factorial(temp) / math.factorial(temp - count_left) / \
                 math.factorial(count_left) * math.factorial(count_total)
    else:
        result = 0

    # Now find duplicate-involving combinations
    for member in set(unprocessed):
        valid = True
        for contest in choices_picked:
            if contest >= member:
                valid = False
                break

        if valid:
            count = unprocessed.count(member)
            new_choices = choices_picked + [ member ]
            for i in range(2, count+1):
                result_temp = cnt_unique(aset, new_choices, \
                  count_left - i, count_total)
                if result_temp != 0:
                    result_temp //= math.factorial(i)
                    result += result_temp
    return result

aset = [ 1, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
result_size = 4
combinations = cnt_unique(aset, [], result_size, result_size)

OK, I've verified by hand that algorithm works for all of your cases presented above. I'm fairly confident it works in more general cases, but I don't have time at the moment to do any additional test cases (for instance, if there were 3 1's, or 3 groups of duplicates). Note it would also blow up if there were no numbers in set which were not in choices_picked (ie you have one unique number duplicated 10 times).

Edit 3: Regarding how many function calls are made with this algorithm for large sets, I tested with the following function call, incrementing a variable once for each non-trivial (count_left >= 0) call to cnt_unique:

>>> def test():
        b = [0]
        c = time.time()
        result = cnt_unique(range(1,51) + range(1,51), [], 4, 4, b)
        c = time.time() - c
        print("Result: " + str(result))
        print("Time: " + str(c))
        print("Calls: " + str(b[0]))

>>> test()
Result: 6240150
Time: 0.0150001049042
Calls: 1276

So, for a 100 element set with 2 entries for each number 1-50, there were 1276 calls. And it executes quite fast; one tick with time.time() is 15 ms, so it executes in typically less than 15 ms.

Answer 4

If you need to do this on any set larger than your example, watch out for overflows in your intermediate calculations. 13! is already large enough to overflow a 32-bit UINT. Only a few larger than that will overflow 64 bits. Using float/double isn't any better since you'll get the wrong answer without full precision.

You would need to use an arbitrary precision integer class or some custom numeric class that carries the full list of factors when calculating the factorial or any multiplies, then doing factor elimination to simplify the division.

Answer 5

You need to break the problem in 2 cases:

Case 1: zero or one "1" in your 4-digit number Number of permutation is 9! / (9-4)! = 3024

Case 2: two "1"s in your 4-digit number You know two of the digits must be 1, so there are 8*7 ways to select the remaining two digits. And there are (4! / 2!) ways to arrange the two "1"s and two other digits. Hence, the number of permutation is 8*7*(4! / 2!) = 672

It looks like the answer is 3024+672 = 3696