0

I would like to calculate possible combinations for a given set of data:

There is an x amount of columns (let's say 3) each column contains y amount of words (lets say 2), now I would like to calculate total amount of permutations possible, the thing is that columns may have common elements and repetition is not allowed, i.e you can't choose the same elements twice or more

For example: column 1 contains "one" and "two", column 2 contains "one" and "four", column 3 contains "four" and "six" then all possible combinations are:

["one", "four", "six"], ["two", "one", "four"], ["two", "one", "six"], ["two", "four", "six"], That's 4, how I can calculate that, is there a closed form or recursive form solution for large matrices?

Samadi
  • 11
  • So the columns can contain repeats, and you want to count selections of one item from each column in which such selections do not contain repeats, if I get your meaning. In that case the count will depend of course on the compositions of the various columns, not just how many columns and rows. It seems to me there may not be a "closed form" answer, unless it is in terms of what all the columns look like. – coffeemath Jun 15 '15 at 03:43
  • Yes, that's exactly what I mean, I suppose there should be a recursive form of solution to this question but I haven't figured it out yet. – Samadi Jun 17 '15 at 04:51

1 Answers1

0

this problem is called Systems of distinct representatives

Let S1, S2, ..., Sm be subsets (not necessarily distinct) of an n-set with m ≤ n. The incidence matrix of this collection of subsets is an m × n (0,1)-matrix A. The number of systems of distinct representatives (SDR's) of this collection is perm(A). In mathematics, an incidence matrix is a matrix that shows the relationship between two classes of objects. If the first class is X and the second is Y, the matrix has one row for each element of X and one column for each element of Y. The entry in row x and column y is 1 if x and y are related (called incident in this context) and 0 if they are not. the incidence matrix for our example above would be A=[1 1 0 0; 1 0 1 0; 0 0 1 1], where rows correspond to columns in our example and columns correspond to the choices we have,"one", "two", "four" and "six" respectively.

Samadi
  • 11