Need help in a permutation problem

Правка en1, от Ayushrusiya47, 2023-11-08 00:01:52

You are given an array of arrays $$$A$$$ containing integers of the range $$$[1, N]$$$. Now you need to select one element from every array present in $$$A$$$ such that no two elements are same i.e. you need to make a permutation of length $$$N$$$ such that element at $$$i_{th}$$$ index is present in the array $$$A_i$$$. Also find the number of permutations that satisfy this condition.

For example:

A = [
     [1,2,5],
     [3],
     [2,4],
     [1,4,5],
     [1,3]
    ]

[2, 3, 4, 5, 1] will be a valid permutation for this case.

I think I have seen this problem as a subproblem in some questions, but I can not think of anything other than brute force.

Thanks.

Теги permutations, constructive

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский Ayushrusiya47 2023-11-08 00:01:52 714 Initial revision (published)