Amount of arrays with unique numbers

user_17201508 0
Viewed 76

I have been wondering if there is any better solution of this problem: Let's assume that there are n containers (they might not have the same length). In each of them we have some numbers. What is the amount of n-length arrays that are created by taking one element from every container? Those numbers in the newly formed arrays must be unique (e.g. (2,3,3) can not be created but (2,4,3) can). Here is an exaple:

n=3

c1=(1,6,7)

c2=(1,6,7)

c3=(6,7)

The correct answer is 4, because we can create those four arrays: (1,6,7), (1,7,6), (6,1,7), (6,7,1).

Edit: None of the n containers contain duplicates and all the elements in the new arrays must have the same order as the order of the containers they belong to.

So my question is: Is there any better way to calculate the number of those arrays than just by generating every single possibility and checking if it has no repetitions?

combinations algorithm
1 Answers

You do not need to generate each possibility and then check whether or not it has repetitions - you can do that before adding the would-be duplicate element, saving a lot of wasted work further down the line. But yes, given the requirement that

all the elements in the new arrays must have the same order as the order of the containers they belong to

you cannot simply count permutations, or combinations of m-over-n, which would have been much quicker (as there is a closed formula for those).

Therefore, the optimal algorithm is probably to use a backtracking approach with a set to avoid duplicates while building partial answers, and count the number of valid answers found.

The problem looks somewhat like counting possible answers to a 1-dimensional sudoku: choose one element each from each region, ensuring no duplicates. For many cases, there may be 0 answers - imagine n=4, c=[[1,2],[2,3],[3,1],[2,3]]. For example, if are less than k unique elements for a subset of k containers, no answer is possible.

user_154720
Related