A Statisical problem - Programmers Heaven

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

A Statisical problem

earth_walkerearth_walker Posts: 184Member
A, B are sets
A={10, 9, 8, 7, 6, 5, 4, 3}
B={6, 5, 4, 3, 2, 1}
now we want to pick 3 elements from A to form a new set subA, and 3 elements from B to form subB. subA and subB don't have common elements.

How to list all possible combinations of subA and subB?
Is it possible to find an general algorithm to solve this problem?

Any comments, method description, psudocode, or actual related can be helpful to me.

Thank you very much!

Comments

  • nightsurfernightsurfer Posts: 272Member
    OK, here's a go at a possible algorithm, or at least the start of one. Make two lists of subsets, Asub and Bsub. Then for each set in Asub, list all the possible combos with the sets in Bsub in a new list, subPairs. When you have finished going through Asub, you will have finished all the possible pairs of subsets of A and B containing 3 elements each, with no common elements.

    : A, B are sets
    : A={10, 9, 8, 7, 6, 5, 4, 3}
    : B={6, 5, 4, 3, 2, 1}
    : now we want to pick 3 elements from A to form a new set subA, and 3 elements from B to form subB. subA and subB don't have common elements.
    :
    : How to list all possible combinations of subA and subB?
    : Is it possible to find an general algorithm to solve this problem?
    :
    : Any comments, method description, psudocode, or actual related can be helpful to me.
    :
    : Thank you very much!
    :

    There are two methods in software design. One is to make the program so simple, there are obviously no errors. The other is to make it so complicated, there are no obvious errors.

  • earth_walkerearth_walker Posts: 184Member
    Thank you! There is a sub-problem which I can not solve well now. Can you tell me how to list all subsets with certain size of a set?
    For example, list all 3-element subsets of {1,2,3,4,5,6}
    Thank you very much!

    : OK, here's a go at a possible algorithm, or at least the start of one. Make two lists of subsets, Asub and Bsub. Then for each set in Asub, list all the possible combos with the sets in Bsub in a new list, subPairs. When you have finished going through Asub, you will have finished all the possible pairs of subsets of A and B containing 3 elements each, with no common elements.
    :
    : : A, B are sets
    : : A={10, 9, 8, 7, 6, 5, 4, 3}
    : : B={6, 5, 4, 3, 2, 1}
    : : now we want to pick 3 elements from A to form a new set subA, and 3 elements from B to form subB. subA and subB don't have common elements.
    : :
    : : How to list all possible combinations of subA and subB?
    : : Is it possible to find an general algorithm to solve this problem?
    : :
    : : Any comments, method description, psudocode, or actual related can be helpful to me.
    : :
    : : Thank you very much!
    : :
    :
    : There are two methods in software design. One is to make the program so simple, there are obviously no errors. The other is to make it so complicated, there are no obvious errors.
    :
    :

  • nightsurfernightsurfer Posts: 272Member
    OK, I think the way to do it is to start by calculating how many subsets there are (it's just the combination nCp to make sets of size p from a single set with n elements). From there, you start by determining the number of sets with one less element (in your case, 2).

    When you are down to 1 element subsets, you assign each element to (nCp)/n of the subsets. For the next element, you assign each of the remaining numbers to ((nCp)/n)/(n-1). Continue until you have all the sets filled.

    EXAMPLE
    {1, 2, 3, 4}

    nCp = 4C3 = 24/(6*1) = 4

    {1, x, x}, {2, x, x}, {3, x, x}, {4, x, x}

    {1, 2, x}, {2, 3, x}, {3, 4, x}, {4, 1, x}

    {1, 2, 3}, {2, 3, 4}, {3, 4, 1}, {4, 1, 2}

    EXAMPLE
    {1, 2, 3, 4, 5}

    nCp = 5C3 = 120/(6*2) = 10

    {1, x, x}, {2, x, x}, {3, x, x}, {4, x, x}, {5, x, x}, {1, x, x}, {2, x, x}, {3, x, x}, {4, x, x}, {5, x, x}

    {1, 2, x}, {2, 3, x}, {3, 4, x}, {4, 5, x}, {5, 1, x}, {1, 2, x}, {2, 3, x}, {3, 4, x}, {4, 5, x}, {5, 1, x}

    {1, 2, 3}, {2, 3, 4}, {3, 4, 5}, {4, 5, 1}, {5, 1, 2}, {1, 2, 4}, {2, 3, 5}, {3, 4, 1}, {4, 5, 2}, {5, 1, 3}

    I hope this helps.

    : Thank you! There is a sub-problem which I can not solve well now. Can you tell me how to list all subsets with certain size of a set?
    : For example, list all 3-element subsets of {1,2,3,4,5,6}
    : Thank you very much!
    :
    : : OK, here's a go at a possible algorithm, or at least the start of one. Make two lists of subsets, Asub and Bsub. Then for each set in Asub, list all the possible combos with the sets in Bsub in a new list, subPairs. When you have finished going through Asub, you will have finished all the possible pairs of subsets of A and B containing 3 elements each, with no common elements.
    : :
    : : : A, B are sets
    : : : A={10, 9, 8, 7, 6, 5, 4, 3}
    : : : B={6, 5, 4, 3, 2, 1}
    : : : now we want to pick 3 elements from A to form a new set subA, and 3 elements from B to form subB. subA and subB don't have common elements.
    : : :
    : : : How to list all possible combinations of subA and subB?
    : : : Is it possible to find an general algorithm to solve this problem?
    : : :
    : : : Any comments, method description, psudocode, or actual related can be helpful to me.
    : : :
    : : : Thank you very much!
    : : :
    : :
    : : There are two methods in software design. One is to make the program so simple, there are obviously no errors. The other is to make it so complicated, there are no obvious errors.
    : :
    : :
    :
    :

    There are two methods in software design. One is to make the program so simple, there are obviously no errors. The other is to make it so complicated, there are no obvious errors.

  • earth_walkerearth_walker Posts: 184Member
    Thank you very much for your help! I think at least I know how it implement it now.


    : OK, I think the way to do it is to start by calculating how many subsets there are (it's just the combination nCp to make sets of size p from a single set with n elements). From there, you start by determining the number of sets with one less element (in your case, 2).
    :
    : When you are down to 1 element subsets, you assign each element to (nCp)/n of the subsets. For the next element, you assign each of the remaining numbers to ((nCp)/n)/(n-1). Continue until you have all the sets filled.
    :
    : EXAMPLE
    : {1, 2, 3, 4}
    :
    : nCp = 4C3 = 24/(6*1) = 4
    :
    : {1, x, x}, {2, x, x}, {3, x, x}, {4, x, x}
    :
    : {1, 2, x}, {2, 3, x}, {3, 4, x}, {4, 1, x}
    :
    : {1, 2, 3}, {2, 3, 4}, {3, 4, 1}, {4, 1, 2}
    :
    : EXAMPLE
    : {1, 2, 3, 4, 5}
    :
    : nCp = 5C3 = 120/(6*2) = 10
    :
    : {1, x, x}, {2, x, x}, {3, x, x}, {4, x, x}, {5, x, x}, {1, x, x}, {2, x, x}, {3, x, x}, {4, x, x}, {5, x, x}
    :
    : {1, 2, x}, {2, 3, x}, {3, 4, x}, {4, 5, x}, {5, 1, x}, {1, 2, x}, {2, 3, x}, {3, 4, x}, {4, 5, x}, {5, 1, x}
    :
    : {1, 2, 3}, {2, 3, 4}, {3, 4, 5}, {4, 5, 1}, {5, 1, 2}, {1, 2, 4}, {2, 3, 5}, {3, 4, 1}, {4, 5, 2}, {5, 1, 3}
    :
    : I hope this helps.
    :
    : : Thank you! There is a sub-problem which I can not solve well now. Can you tell me how to list all subsets with certain size of a set?
    : : For example, list all 3-element subsets of {1,2,3,4,5,6}
    : : Thank you very much!
    : :
    : : : OK, here's a go at a possible algorithm, or at least the start of one. Make two lists of subsets, Asub and Bsub. Then for each set in Asub, list all the possible combos with the sets in Bsub in a new list, subPairs. When you have finished going through Asub, you will have finished all the possible pairs of subsets of A and B containing 3 elements each, with no common elements.
    : : :
    : : : : A, B are sets
    : : : : A={10, 9, 8, 7, 6, 5, 4, 3}
    : : : : B={6, 5, 4, 3, 2, 1}
    : : : : now we want to pick 3 elements from A to form a new set subA, and 3 elements from B to form subB. subA and subB don't have common elements.
    : : : :
    : : : : How to list all possible combinations of subA and subB?
    : : : : Is it possible to find an general algorithm to solve this problem?
    : : : :
    : : : : Any comments, method description, psudocode, or actual related can be helpful to me.
    : : : :
    : : : : Thank you very much!
    : : : :
    : : :
    : : : There are two methods in software design. One is to make the program so simple, there are obviously no errors. The other is to make it so complicated, there are no obvious errors.
    : : :
    : : :
    : :
    : :
    :
    : There are two methods in software design. One is to make the program so simple, there are obviously no errors. The other is to make it so complicated, there are no obvious errors.
    :
    :

Sign In or Register to comment.