#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2013
    Posts
    2
    Rep Power
    0

    Arrange given sets on given number of blanks


    We are given N distinct elements divided into S non empty sets.

    #elements in the sets are a1, a2, a3... aS s.t.
    a1+a2+a3+...+aS=N
    We are given M positions s.t.
    M>=S && M<=N

    At least one element from each set must be present in the arrangement.
    Each element can be placed only once.
    Two arrangements are different if all the elements present in both arrangement are not same.
    How many such arrangements are possible?

    Eg. {1,2,3}, {4,5}
    4 blanks _ _ _ _
    ANS: 5

    1 4 2 3
    1 4 3 5
    1 4 2 5
    1 5 2 3
    2 4 3 5


    How will we solve this type of problems? Is there any formula we can create?
  2. #2
  3. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2013
    Posts
    5
    Rep Power
    0
    Do you need to know the actual arrangements, or just the number of possible arrangements? The method is totally different.

    If you only need to know the number of arrangements, the you only need the number of items in the arrays, not even what they are.

    If you need to know the actual arrangements, then you can simply iterate allthe matching patterns and count them.


    Matt
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2013
    Posts
    2
    Rep Power
    0
    Originally Posted by travellingmatt
    Do you need to know the actual arrangements, or just the number of possible arrangements? The method is totally different.

    If you only need to know the number of arrangements, the you only need the number of items in the arrays, not even what they are.

    If you need to know the actual arrangements, then you can simply iterate allthe matching patterns and count them.


    Matt
    Thanks for reply travellingmatt.
    I need to know number of arrangements only. And yes u are right that I need to know #items in the arrays only. But I am not able to find how to do so. Please help...

IMN logo majestic logo threadwatch logo seochat tools logo