+ Reply to Thread
Results 1 to 14 of 14

Generating all subsets of a given size from a set of integers

  1. #1
    Registered User
    Join Date
    05-24-2011
    Location
    London, England
    MS-Off Ver
    Excel 2013
    Posts
    36

    Generating all subsets of a given size from a set of integers

    How can I find all the ways to divide a set of 12 distinct integers into 3 subsets each containing 4 of the integers?

    Suppose the integers are {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} then I want to output all sets A, B and C that each have 4 elements.
    One possibility is A = {1, 2, 3, 4} , B = {5, 6, 7, 8} and C = {9, 10, 11, 12}
    I don't want repeats (for example A = {5, 6, 7, 8} , B = {1, 2, 3, 4} and C = {9, 10, 11, 12} counts as a repeat since the 3 sets are the same but in a different order)

  2. #2
    Forum Expert shg's Avatar
    Join Date
    06-20-2007
    Location
    The Great State of Texas
    MS-Off Ver
    2003, 2010
    Posts
    40,678

    Re: Generating all subsets of a given size from a set of integers

    Count the ways?

    =COMBIN(12, 4) * COMBIN(8, 4) = 34650
    Entia non sunt multiplicanda sine necessitate

  3. #3
    Registered User
    Join Date
    05-24-2011
    Location
    London, England
    MS-Off Ver
    Excel 2013
    Posts
    36

    Re: Generating all subsets of a given size from a set of integers

    shg, I don't wish to count the ways (and if I did I would say that your answer is wrong because you need to allow for the arrangements of the 3 subsets). For example {A, B, C} is the same as {B, A, C}.

    I wish to know how to output the list of subsets, please.

  4. #4
    Forum Expert shg's Avatar
    Join Date
    06-20-2007
    Location
    The Great State of Texas
    MS-Off Ver
    2003, 2010
    Posts
    40,678

    Re: Generating all subsets of a given size from a set of integers

    Quote Originally Posted by Bananabean View Post
    I would say that your answer is wrong because you need to allow for the arrangements of the 3 subsets
    "Allow for the arrangement of the subset"?? For example?

    What do you think the answer is?

  5. #5
    Registered User
    Join Date
    05-24-2011
    Location
    London, England
    MS-Off Ver
    Excel 2013
    Posts
    36

    Re: Generating all subsets of a given size from a set of integers

    I would say it was 12C4 * 8C4 / 3! = 5775 but I might be wrong.
    I divided by 3! because that is the number of ways to arrange 3 different objects among themselves.

    12C4 * 8C4 is the number of ways to put the digits into 3 subsets but, as I said, I count (A, B, C) to be a repeat of (C, A, B)

  6. #6
    Forum Expert shg's Avatar
    Join Date
    06-20-2007
    Location
    The Great State of Texas
    MS-Off Ver
    2003, 2010
    Posts
    40,678

    Re: Generating all subsets of a given size from a set of integers

    That is indeed wrong.

    The first set can be any combination of 12C4, the second any combination of 8C4, and the third is what's left.

  7. #7
    Registered User
    Join Date
    05-24-2011
    Location
    London, England
    MS-Off Ver
    Excel 2013
    Posts
    36

    Re: Generating all subsets of a given size from a set of integers

    shg, my apologies. Your logic seems correct.

    On second thoughts it does not.
    One of the ways you are counting is A = {1, 2, 3, 4}, B = {5, 6, 7, 8} and so C = {9, 10 , 11 ,12}
    You are counting this outcome as though it is different: A = {1, 2, 3, 4}, B = {9, 10 , 11 ,12} and so B = {5, 6, 7, 8}
    However these two outcomes are the same since order doesn't matter. Only the set contents matter and in both cases they are the same.
    Last edited by Bananabean; 08-18-2019 at 02:39 PM. Reason: I think the answer is wrong

  8. #8
    Forum Expert shg's Avatar
    Join Date
    06-20-2007
    Location
    The Great State of Texas
    MS-Off Ver
    2003, 2010
    Posts
    40,678

    Re: Generating all subsets of a given size from a set of integers

    This will generate the first two sets. I'll leave the "what's left" part to you.

    Please Login or Register  to view this content.

  9. #9
    Forum Expert shg's Avatar
    Join Date
    06-20-2007
    Location
    The Great State of Texas
    MS-Off Ver
    2003, 2010
    Posts
    40,678

    Re: Generating all subsets of a given size from a set of integers

    Partial output:

    A
    B
    C
    D
    E
    F
    G
    H
    1
    4
    3
    2
    1
    8
    7
    6
    5
    2
    4
    3
    2
    1
    9
    7
    6
    5
    3
    4
    3
    2
    1
    9
    8
    6
    5
    4
    4
    3
    2
    1
    9
    8
    7
    5
    5
    4
    3
    2
    1
    9
    8
    7
    6
    6
    4
    3
    2
    1
    10
    7
    6
    5
    7
    4
    3
    2
    1
    10
    8
    6
    5
    8
    4
    3
    2
    1
    10
    8
    7
    5
    9
    4
    3
    2
    1
    10
    8
    7
    6
    10
    4
    3
    2
    1
    10
    9
    6
    5
    34636
    12
    11
    10
    9
    8
    7
    2
    1
    34637
    12
    11
    10
    9
    8
    7
    3
    1
    34638
    12
    11
    10
    9
    8
    7
    3
    2
    34639
    12
    11
    10
    9
    8
    7
    4
    1
    34640
    12
    11
    10
    9
    8
    7
    4
    2
    34641
    12
    11
    10
    9
    8
    7
    4
    3
    34642
    12
    11
    10
    9
    8
    7
    5
    1
    34643
    12
    11
    10
    9
    8
    7
    5
    2
    34644
    12
    11
    10
    9
    8
    7
    5
    3
    34645
    12
    11
    10
    9
    8
    7
    5
    4
    34646
    12
    11
    10
    9
    8
    7
    6
    1
    34647
    12
    11
    10
    9
    8
    7
    6
    2
    34648
    12
    11
    10
    9
    8
    7
    6
    3
    34649
    12
    11
    10
    9
    8
    7
    6
    4
    34650
    12
    11
    10
    9
    8
    7
    6
    5

  10. #10
    Registered User
    Join Date
    05-24-2011
    Location
    London, England
    MS-Off Ver
    Excel 2013
    Posts
    36

    Re: Generating all subsets of a given size from a set of integers

    Thank you very much for this, shg.

  11. #11
    Forum Expert shg's Avatar
    Join Date
    06-20-2007
    Location
    The Great State of Texas
    MS-Off Ver
    2003, 2010
    Posts
    40,678

    Re: Generating all subsets of a given size from a set of integers

    You're welcome.

  12. #12
    Forum Expert shg's Avatar
    Join Date
    06-20-2007
    Location
    The Great State of Texas
    MS-Off Ver
    2003, 2010
    Posts
    40,678

    Re: Generating all subsets of a given size from a set of integers

    I owe you an apology -- your result of 5775 combinations is correct.

    Haven't figured out how to generate them.
    Last edited by shg; 08-19-2019 at 11:29 AM.

  13. #13
    Registered User
    Join Date
    05-24-2011
    Location
    London, England
    MS-Off Ver
    Excel 2013
    Posts
    36

    Re: Generating all subsets of a given size from a set of integers

    Thanks, shg, I have managed to generate them but I used sneaky methods rather than VBA.
    I found the third column for each of the 34650 rows and concatenated each set A, B, C into a single number.
    Then I found the product of the three numbers A*B*C, sorted by this product and removed duplicates leaving the 5775 different triples.

  14. #14
    Forum Expert shg's Avatar
    Join Date
    06-20-2007
    Location
    The Great State of Texas
    MS-Off Ver
    2003, 2010
    Posts
    40,678

    Re: Generating all subsets of a given size from a set of integers

    Good job, and sorry for the misdirection.

+ Reply to Thread

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Similar Threads

  1. [SOLVED] A list of Consecutive Integers, can I search for missing integers
    By CM in forum Excel Formulas & Functions
    Replies: 4
    Last Post: 09-07-2005, 12:05 AM
  2. [SOLVED] A list of Consecutive Integers, can I search for missing integers
    By Harlan Grove in forum Excel Formulas & Functions
    Replies: 8
    Last Post: 09-06-2005, 11:05 PM
  3. [SOLVED] A list of Consecutive Integers, can I search for missing integers
    By CM in forum Excel Formulas & Functions
    Replies: 0
    Last Post: 09-06-2005, 04:05 PM
  4. A list of Consecutive Integers, can I search for missing integers
    By CM in forum Excel Formulas & Functions
    Replies: 0
    Last Post: 09-06-2005, 03:05 PM
  5. [SOLVED] A list of Consecutive Integers, can I search for missing integers
    By CM in forum Excel Formulas & Functions
    Replies: 0
    Last Post: 09-06-2005, 12:05 PM
  6. [SOLVED] A list of Consecutive Integers, can I search for missing integers
    By Harlan Grove in forum Excel Formulas & Functions
    Replies: 12
    Last Post: 09-06-2005, 08:05 AM
  7. [SOLVED] A list of Consecutive Integers, can I search for missing integers
    By CM in forum Excel Formulas & Functions
    Replies: 0
    Last Post: 09-06-2005, 07:05 AM
  8. [SOLVED] A list of Consecutive Integers, can I search for missing integers
    By CM in forum Excel Formulas & Functions
    Replies: 4
    Last Post: 09-02-2005, 02:05 PM

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts

Search Engine Friendly URLs by vBSEO 3.6.0 RC 1