Win a copy of Pipeline as Code this week in the Cloud/Virtualization forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Ron McLeod
  • Paul Clapham
  • Jeanne Boyarsky
  • Bear Bibeault
Sheriffs:
  • Rob Spoor
  • Henry Wong
  • Liutauras Vilda
Saloon Keepers:
  • Tim Moores
  • Carey Brown
  • Stephan van Hulst
  • Tim Holloway
  • Piet Souris
Bartenders:
  • Frits Walraven
  • Himai Minh
  • Jj Roberts

Is power set WITH duplicates a thing?

 
Ranch Hand
Posts: 38
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hello all,

Well, when it rains, it pours. When I find myself on code ranch, it's usually because I have 5 or 25 questions, not just 1! Here I go again for the 2nd time in 2 days!

I'm looking for a tidy way to assemble every possible combination for arguments I'm feeding to a test.

I have, for example, and array of integers from 4, 7 (inclusive): [ 4, 5, 6, 7 ]

I'd like to basically build the power set. I find lots of useful stuff on the web for building a power set from an array in java. However, I want to include [ 4, 5 ] AND [ 5, 4 ]. A typical power set omits these, as they're considered duplicate. My tests does different things with the 1st or the second item in that subset, so I want to preserve "duplicates".

My current code is:


This code is not mine, it's adapted from Matt McPeak here: https://stackoverflow.com/questions/5162254/all-possible-combinations-of-an-array

This code is great, but it doesn't allow duplicates ( it includes [5, 6] but not [6, 5]). Any feedback is welcomed. Does this problem go by a different name?

Many thanks,
 
Marshal
Posts: 26475
81
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Just to clarify:

Normally if you started with the set {1, 2, 3} then the power set of that would be {{}, {1}, {2}, {3}, {1, 2}. {1, 3}, {2, 3}, {1, 2, 3}}. Since the original set had 3 elements, the power set has 2^3 = 8 elements.

But if I understand it correctly you don't exactly want a power set. You want a set consisting of {[], [1], [2], [3], [1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], [3, 3], [1, 1, 1], [1, 1, 2], [1, 1, 3], [1, 2, 1], [1, 2, 2], [1, 2, 3], [1, 3, 1]... (remainder left as an exercise for the student)}. This set has 1 + 3 + 9 + 27 = 40 elements.

Or am I not understanding correctly?
 
Simon McNamara
Ranch Hand
Posts: 38
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hey Paul,

Yes, you've got it exactly. I do recognize that this is not a power set, strictly speaking. I thought perhaps this is a well-known problem of which I don't know the name!

Thanks for your time,
 
Marshal
Posts: 72441
315
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
It sounds like a kind of product; it is too late to go through my Maths book looking for the type of product, but we are promoting that selfsame Maths book soon, so ask a question where the promotion appears and you might be lucky.
[addition]And no, there is no such thing as a set with duplicate elements. If you seem to have duplicates, it is because of incorrect implementation of the equals() method: remember there are eight things you have to ensure.
 
Paul Clapham
Marshal
Posts: 26475
81
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Okay. I was unclear because you said you wanted to include [4, 5] and [5, 4] but you didn't say whether you wanted to include [4, 4].

I don't know a name for your data structure, even after searching the web for a while. You want the set of all multisets of elements of a base set S? It looks like it's not even that. You want the set of all tuples of elements of a base set S.

Edit: However it looks like you'd want to have a limit on the length of the tuples, so that you couldn't have [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...] from the base set {1}. Otherwise you're going to produce an infinite set as the result.
 
Saloon Keeper
Posts: 8008
70
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Doesn't answer your question...but I noticed this:
The later is probably much quicker (premature optimization).
 
Simon McNamara
Ranch Hand
Posts: 38
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Darn.

After some more googling, I think I can better describe what I want as all possible permutations of an array. From what I've seen, all permutations of some array [a, b, c] necessarily involves the many combinations of only 3-item arrays (each resulting array is 3-items long).

This may seem hackey, but perhaps I can retrieve those permutations, decrement my array by one object, compute those permutations, and so on, until I've exhausted my array. Then, I can mash all of the arrays together.

Unless one of you tries to stop me, I might just try this. Really though, if you suggests an easier solution, I'm all ears.

Thanks for your feedback,
 
Paul Clapham
Marshal
Posts: 26475
81
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I see. So "WITH" duplicates isn't quite so capitalized now  :)

From {1, 2, 3} you want {[], [1], [2], [3], [1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2], [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]}.

This is what Sloane's list calls "[The] ordered k-tuples (k=0..n) of distinct elements from an n-element set". https://oeis.org/A000522 These numbers look like they are O(n!) but hopefully n isn't going to be larger than about 5.
 
Simon McNamara
Ranch Hand
Posts: 38
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks Paul!

Yes, what you describe is what I'd like! What a name, huh?

Would anyone happen to know of an implementation of such an esoteric combination?

Many thanks,
 
Paul Clapham
Marshal
Posts: 26475
81
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I looked at what it takes to go from n=1 to n=2 for a start. For n=1 you've got the two tuples [] and [1], and for n=2 you've got the five tuples [], [1], [2], [12], and [21]. You need to take the two tuples for n=1 and strategically put in some 2's to get the five tuples for n=2.

So let's see how that might be done. Let's keep the original two tuples unchanged for a start, that's [] and [1]. Next let's make modified versions by tacking on 2: that's [2] from the first and [12] and [21] from the second. That gives us the five. All righty then!

Does that work going on to n=3, where we need 16 tuples? We start with the original five: [], [1], [2], [12], and [21]. We keep them. Now we're going to make modified versions by tacking on 3: that's [3] from the first, [13] and [31] from the second, [23] and [32] from the third. The fourth gives us [123], [132], and [312], and the fifth gives us [213], [231], and [213]. Did that work? We had five and we needed eleven more... check.

So that's my algorithm. If we have a tuple with k digits, then tacking on the digit for the next level results in k+1 new tuples.
 
Simon McNamara
Ranch Hand
Posts: 38
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Paul,

On my way to a solution, I'm strangely confused.

I'm trying here to get all combinations of two lists, where the first list is the 1st dimension of the list and the 2nd list is the 2nd dimension of the list.

args = [ [ 1, 2 ], [8, 9] ]

Why doesn't this work?:



I'm getting:
[1, 2], [1, 2], [8, 9], [8, 9],

Instead of (what I expect):
[1,8], [1,9], [2,8], [2,9]

I don't often work with Lists, maybe I'm missing something in the API.

Thanks for your time.
 
Saloon Keeper
Posts: 4357
163
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
You should go one level deeper:
 
Simon McNamara
Ranch Hand
Posts: 38
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks Piet, that was driving me bonkers.

I've returned to the question of building the set of all possible combinations (with "duplicates") as discussed earlier. I've started with some version of the pseudo code that Paul suggested.

For an example List = [5, 6, 7], I can get all possible combination of two elements with this:



So, obviously, I place a call to List.add() with two indices as arguments, so I'll only ever get combinations of two items. I'm now trying to generalize this to start by adding all combinations of 3 items, decrementing my list, adding all combinations of 2 items, and so on. However I'm having some trouble figuring out how to add a series of 3 indices. Any suggestions for this?
 
Piet Souris
Saloon Keeper
Posts: 4357
163
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
See this link (click here) where Paul Orland gives a very short solution.
Myself, I use a Map where the key is an integer, and the value is a List of all subsets of that length. That is how I implemented Paul Claphams algo.
 
Campbell Ritchie
Marshal
Posts: 72441
315
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Piet Souris wrote:. . . Paul Orland gives a very short solution. . . .

Short, but good. I shall have to win that book; then I can have two copies.
 
Simon McNamara
Ranch Hand
Posts: 38
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Wow that's such a succinct solution. I don't know python very well, but I'll try my hand at translating that to java!
 
Piet Souris
Saloon Keeper
Posts: 4357
163
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:

Piet Souris wrote:. . . Paul Orland gives a very short solution. . . .

Short, but good. I shall have to win that book; then I can have two copies.


Ho ho, I was first!!      
 
There's a way to do it better - find it. -Edison. A better tiny ad:
SKIP - a book about connecting industrious people with elderly land owners
https://coderanch.com/t/skip-book
reply
    Bookmark Topic Watch Topic
  • New Topic