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

- 140.9K All Categories
- 104.4K Programming Languages
- 6.4K Assembler Developer
- 1.8K Basic
- 39.8K C and C++
- 4.2K C#
- 7.9K Delphi and Kylix
- 4 Haskell
- 9.6K Java
- 4.1K Pascal
- 1.3K Perl
- 1.9K PHP
- 507 Python
- 48 Ruby
- 4.3K VB.NET
- 1.6K VBA
- 20.8K Visual Basic
- 2.6K Game programming
- 310 Console programming
- 88 DirectX Game dev
- 1 Minecraft
- 110 Newbie Game Programmers
- 2 Oculus Rift
- 8.9K Applications
- 1.8K Computer Graphics
- 726 Computer Hardware
- 3.4K Database & SQL
- 521 Electronics development
- 1.6K Matlab
- 627 Sound & Music
- 256 XML Development
- 3.3K Classifieds
- 194 Co-operative Projects
- 181 For sale
- 189 FreeLance Software City
- 1.9K Jobs Available
- 600 Jobs Wanted
- 201 Wanted
- 2.9K Microsoft .NET
- 1.7K ASP.NET
- 1.1K .NET General
- 3.1K Miscellaneous
- 3 Join the Team
- 0 User Profiles
- 349 Comments on this site
- 59 Computer Emulators
- 1.9K General programming
- 178 New programming languages
- 596 Off topic board
- 160 Mobile & Wireless
- 34 Android
- 124 Palm Pilot
- 335 Multimedia
- 151 Demo programming
- 184 MP3 programming
- 0 Bash scripts
- 18 Cloud Computing
- 52 FreeBSD
- 1.7K LINUX programming
- 367 MS-DOS
- 0 Shell scripting
- 320 Windows CE & Pocket PC
- 4.1K Windows programming
- 882 Software Development
- 405 Algorithms
- 68 Object Orientation
- 86 Project Management
- 88 Quality & Testing
- 234 Security
- 7.5K WEB-Development
- 1.8K Active Server Pages
- 61 AJAX
- 2 Bootstrap Themes
- 55 CGI Development
- 19 ColdFusion
- 222 Flash development
- 1.4K HTML & WEB-Design
- 1.4K Internet Development
- 2.2K JavaScript
- 33 JQuery
- 285 WEB Servers
- 130 WEB-Services / SOAP

earth_walker
Posts: **184**Member

in Algorithms

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!

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!

About & Contact / Terms of use / Privacy statement / Publisher: Lars Hagelin

Programmers Heaven articles / Programmers Heaven files / Programmers Heaven uploaded content / Programmers Heaven C Sharp ebook / Operated by CommunityHeaven LLC

© 1997-2013 Programmersheaven.com - All rights reserved.

## Comments

272Member: 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.

184MemberFor 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.

:

:

272MemberWhen 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.

184Member: 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.

:

: