Necklaces and Bracelets in Combinatorics

This is a discussion on Necklaces and Bracelets in Combinatorics within the C++ Programming forums, part of the General Programming Boards category; Ok, it seems I need some help in understanding and solving the following problem: input : 4 (k) 6 3 ...

  1. #1
    Registered User
    Join Date
    Jan 2012
    Posts
    5

    Necklaces and Bracelets in Combinatorics

    Ok, it seems I need some help in understanding and solving the following problem:
    input :
    4 (k)
    6 3 2 2 2 (n,m,a1,a2,a3)
    6 3 3 2 1 (n,m,a1,a2,a3)
    4 2 2 2
    12 4 6 2 2 2

    output :
    11
    6
    2
    3530
    SO : k is the number of test cases
    n : the number of beads we have available
    m: the colours of the beads we have
    a1,a2,...a : the amount of beads of each colour that we must use.(note that we have m of these numbers)

    For instance with 6 3 2 2 2 we have 6 beads, of 3 colours, and have 2 beads of each colour.
    The question is "what is the maximum number of bracelets we can make using all the beads" ?
    I have done some research on this and have found that the max number of bracelets of n-size and k-colours comes from this function
    http://mathworld.wolfram.com/images/...dEquation2.gif
    but this doesn't seem to implement the fact that you have a limited amount of beads of each colour and basicaly just gives you the amount of bracelets Combinatorial Necklaces and Bracelets - Jason Davies (see here) (if for instance n=6 and k=3, it comes out with 130, when what I want is 6 or 11)
    What do I have to change in order to make it compatible with my specific input ?
    (sry for possible bad english at some points)

    EDIT: THIS http://mathworld.wolfram.com/Necklace.html is a very useful link that explains the function given above.
    Last edited by Stamatis; 03-26-2013 at 01:17 PM.

  2. #2
    Registered User
    Join Date
    Oct 2006
    Posts
    2,499
    how would you do it?

Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21