Solved

Get all subsets of an ArrayList.

Posted on 2013-05-20
6
383 Views
Last Modified: 2013-07-04
I have an ArrayList 'System.Collections.ArrayList' in Powershell which contains a number of numeric items e.g. 5, 10. I am looking for a way I can find all subsets of this array so for the example here it would be...

5,
10
5,10

The order of the sets is not important so set (5, 10) is the same as (10, 5) and am empty set should not count... In reality the array list I have is much larger - any ideas?
0
Comment
Question by:Blowfelt82
6 Comments
 

Author Comment

by:Blowfelt82
ID: 39180355
It also may be important to note that the list may at some point have duplicate items - this is not the case at the moment but would be good to future proof any solution?
0
 
LVL 42

Expert Comment

by:sedgwick
ID: 39180369
what do u mean subsets of this array?
0
 
LVL 19

Expert Comment

by:Raheman M. Abdul
ID: 39180507
Please post atleast 10 items in the array please so that we can get clear idea what the problem is.
0
Backup Solution for AWS

Read about how CloudBerry Backup fully integrates your backups with Amazon S3 and Amazon Glacier to provide military-grade encryption and dramatically cut storage costs on any platform.

 
LVL 27

Accepted Solution

by:
d-glitch earned 500 total points
ID: 39181064
If you have a set of N elements, there will be 2^N subsets including the empty set and the entire set.

The standard way to generate them all is to assign each element to one of the digits in an N-digit binary number.  Then count from 0 to (2^N)-1.

So if your set is [ 15 10 5 ]   your subsets would be ...

000     [  ]             <== empty  set
001     [  5 ]
010     [ 10 ]
011     [ 10 5 ]
100     [  15 ]
...
111     [  15 10 5 ]   <==  entire set

Note that this works with duplicate elements as well.
0
 
LVL 27

Expert Comment

by:d-glitch
ID: 39181991
>>  Note that this works with duplicate elements as well.

Actually, duplicate elements may be a little tricky.

If your set contains duplicates, presumably the subsets can as well.
But the binary counting will generate multiple copies of some subsets.
0
 
LVL 27

Expert Comment

by:d-glitch
ID: 39184356
Suppose your set consists of N items (no duplicates) plus D copies of another item.

The total number of subsets would be  (2^N)*(D+1)

You would generate the subsets of the N unique items as mentioned earlier.
Then you would add 0, 1, 2, ... N copies of the duplicated items.

The mathematics always includes the empty set. You can discard if you wish.

You can extend the math and generation procedure for multiple duplicated items.
0

Featured Post

Free Webinar: AWS Backup & DR

Join our upcoming webinar with experts from AWS, CloudBerry Lab, and the Town of Edgartown IT to discuss best practices for simplifying online backup management and cutting costs.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This article will help you understand what HashTables are and how to use them in PowerShell.
This article explains how to prepare an HTML email signature template file containing dynamic placeholders for users' Azure AD data. Furthermore, it explains how to use this file to remotely set up a department-wide email signature policy in Office …
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…
Exchange organizations may use the Journaling Agent of the Transport Service to archive messages going through Exchange. However, if the Transport Service is integrated with some email content management application (such as an antispam), the admini…

730 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question