472,988 Members | 3,087 Online

# An efficient, pythonic way to calculate result sets

Hello everyone,

I've got a little issue, both programming and performance-wise. I have
a set, containing objects that refer to other sets. For example, in a
simple notation: (<a, b, c>, <d, e>) (or in a more object-like
display: set(obj1.choices=set(a, b, c) ). There may be obj1..objN
objects in the outer set, and the amount of items in the choices sets
could also reach a high number. The objects in the choices sets might
overlap.

Now I want to have all possible combinations, like this: (a, d), (b,
d), (c, d), (a, e), (b, e), (c, e).

However, I've got a few catches that make an already (icky) recursive
function worse to use.

First of all, I want to be able to only choose things so that the
outer 'result sets' have the same length. For example, if you'd have
(<a, b>, <a, c>), you might pick (a, a) with a simple algorythm, the
basic behaviour of sets reducing it to (a) and thus having an improper
length. I could add yet another loop after calculating everything to
throw out any result sets with the improper length, but that would be
highly inefficient.

Second, I'd hope to be able to say that objX should be assumed to have
made the choice z. In the first example I mentioned, if I said that
'obj1 == a', the only result sets that would come out would be (a, d)
and (a, e).

I've been toying with this problem for a while, but I've found out it
quickly gets slow, so I hope some people here could find a way to
write code like this that is efficient (and hopefully not rely on
recursion and 'fix up' loops like I've got mockups with right now).

Thank you for any suggestions you can offer.

Oct 25 '07 #1
6 1346 On Oct 25, 10:31 am, happyhon...@gmail.com wrote:
Hello everyone,

I've got a little issue, both programming and performance-wise. I have
a set, containing objects that refer to other sets. For example, in a
simple notation: (<a, b, c>, <d, e>) (or in a more object-like
display: set(obj1.choices=set(a, b, c) ). There may be obj1..objN
objects in the outer set, and the amount of items in the choices sets
could also reach a high number. The objects in the choices sets might
overlap.

Now I want to have all possible combinations, like this: (a, d), (b,
d), (c, d), (a, e), (b, e), (c, e).

However, I've got a few catches that make an already (icky) recursive
function worse to use.

First of all, I want to be able to only choose things so that the
outer 'result sets' have the same length. For example, if you'd have
(<a, b>, <a, c>), you might pick (a, a) with a simple algorythm, the
basic behaviour of sets reducing it to (a) and thus having an improper
length. I could add yet another loop after calculating everything to
throw out any result sets with the improper length, but that would be
highly inefficient.
Does this do what you want?

result_set = set([])
seta = set(['a','b','c','d','e'])
setb = set(['a','c','f','g','h'])
for i in seta:
temp1 = setb.difference(set([i]))
for j in temp1:
for i in result_set:
print i

I figure there should be 4+5+3+5+5 results.
No ('a'), no ('c'). Has ('a','c') but not ('c','a').

## ('c', 'g')
## ('a', 'd')
## ('h', 'e')
## ('a', 'b')
## ('c', 'f')
## ('e', 'g')
## ('c', 'b')
## ('d', 'f')
## ('a', 'g')
## ('a', 'h')
## ('c', 'e')
## ('e', 'f')
## ('d', 'g')
## ('h', 'b')
## ('a', 'f')
## ('b', 'f')
## ('c', 'd')
## ('h', 'c')
## ('a', 'c')
## ('b', 'g')
## ('a', 'e')
## ('h', 'd')
>
Second, I'd hope to be able to say that objX should be assumed to have
made the choice z. In the first example I mentioned, if I said that
'obj1 == a', the only result sets that would come out would be (a, d)
and (a, e).
Like this?

result_set = set([])
seta = set(['a','b','c','d','e'])
setb = set(['a','c','f','g','h'])
target = 'a'
for i in seta:
temp1 = setb.difference(set([i]))
for j in temp1:
temp2 = set([i,j])
if target in temp2:
for i in result_set:
print i

## ('a', 'f')
## ('a', 'g')
## ('a', 'd')
## ('a', 'e')
## ('a', 'h')
## ('a', 'b')
## ('a', 'c')

>
I've been toying with this problem for a while, but I've found out it
quickly gets slow, so I hope some people here could find a way to
write code like this that is efficient (and hopefully not rely on
recursion and 'fix up' loops like I've got mockups with right now).

Thank you for any suggestions you can offer.

Oct 25 '07 #2
On Oct 25, 8:44 pm, "mensana...@aol.com" <mensana...@aol.comwrote:
On Oct 25, 10:31 am, happyhon...@gmail.com wrote:
Hello everyone,
I've got a little issue, both programming and performance-wise. I have
a set, containing objects that refer to other sets. For example, in a
simple notation: (<a, b, c>, <d, e>) (or in a more object-like
display: set(obj1.choices=set(a, b, c) ). There may be obj1..objN
objects in the outer set, and the amount of items in the choices sets
could also reach a high number. The objects in the choices sets might
overlap.
Now I want to have all possible combinations, like this: (a, d), (b,
d), (c, d), (a, e), (b, e), (c, e).
However, I've got a few catches that make an already (icky) recursive
function worse to use.
First of all, I want to be able to only choose things so that the
outer 'result sets' have the same length. For example, if you'd have
(<a, b>, <a, c>), you might pick (a, a) with a simple algorythm, the
basic behaviour of sets reducing it to (a) and thus having an improper
length. I could add yet another loop after calculating everything to
throw out any result sets with the improper length, but that would be
highly inefficient.

Does this do what you want?

result_set = set([])
seta = set(['a','b','c','d','e'])
setb = set(['a','c','f','g','h'])
for i in seta:
temp1 = setb.difference(set([i]))
for j in temp1:
for i in result_set:
print i

I figure there should be 4+5+3+5+5 results.
No ('a'), no ('c'). Has ('a','c') but not ('c','a').

## ('c', 'g')
## ('a', 'd')
## ('h', 'e')
## ('a', 'b')
## ('c', 'f')
## ('e', 'g')
## ('c', 'b')
## ('d', 'f')
## ('a', 'g')
## ('a', 'h')
## ('c', 'e')
## ('e', 'f')
## ('d', 'g')
## ('h', 'b')
## ('a', 'f')
## ('b', 'f')
## ('c', 'd')
## ('h', 'c')
## ('a', 'c')
## ('b', 'g')
## ('a', 'e')
## ('h', 'd')
Second, I'd hope to be able to say that objX should be assumed to have
made the choice z. In the first example I mentioned, if I said that
'obj1 == a', the only result sets that would come out would be (a, d)
and (a, e).

Like this?

result_set = set([])
seta = set(['a','b','c','d','e'])
setb = set(['a','c','f','g','h'])
target = 'a'
for i in seta:
temp1 = setb.difference(set([i]))
for j in temp1:
temp2 = set([i,j])
if target in temp2:
for i in result_set:
print i

## ('a', 'f')
## ('a', 'g')
## ('a', 'd')
## ('a', 'e')
## ('a', 'h')
## ('a', 'b')
## ('a', 'c')
I've been toying with this problem for a while, but I've found out it
quickly gets slow, so I hope some people here could find a way to
write code like this that is efficient (and hopefully not rely on
recursion and 'fix up' loops like I've got mockups with right now).
Thank you for any suggestions you can offer.
Almost, except for the one big issue that is missing: scalability. I
don't have a seta and setb, but rather set1..setN, with N varying
while the script is running. That's pretty much where the pain comes
in. I have some very (butt-ugly) code that works right now, but it's
more a hack than pretty (or efficient) code.

gave me an idea on another issue I was wrestling with.

Oct 25 '07 #3
On Oct 25, 8:31 am, happyhon...@gmail.com wrote:
I've got a little issue, both programming and performance-wise. I have
a set, containing objects that refer to other sets. For example, in a
simple notation: (<a, b, c>, <d, e>) (or in a more object-like
display: set(obj1.choices=set(a, b, c) ). There may be obj1..objN
objects in the outer set, and the amount of items in the choices sets
could also reach a high number. The objects in the choices sets might
overlap.

Now I want to have all possible combinations, like this: (a, d), (b,
d), (c, d), (a, e), (b, e), (c, e).

However, I've got a few catches that make an already (icky) recursive
function worse to use.

First of all, I want to be able to only choose things so that the
outer 'result sets' have the same length. For example, if you'd have
(<a, b>, <a, c>), you might pick (a, a) with a simple algorythm, the
basic behaviour of sets reducing it to (a) and thus having an improper
length. I could add yet another loop after calculating everything to
throw out any result sets with the improper length, but that would be
highly inefficient.

Second, I'd hope to be able to say that objX should be assumed to have
made the choice z. In the first example I mentioned, if I said that
'obj1 == a', the only result sets that would come out would be (a, d)
and (a, e).
def cross_nodups(*args):
'Cross product after eliminating repeat elements, keeping constant
size'
ans = [[]]
for arg in args:
ans = [x+[y] for x in ans for y in arg if y not in x]
return ans

def choose_first(obj1, *args):
'Assume a choice of a first object'
return cross_nodups(obj1, *args[1:])

>>print cross_nodups('ab', 'acd', 'fg')
[['a', 'c', 'f'], ['a', 'c', 'g'], ['a', 'd', 'f'], ['a', 'd', 'g'],
['b', 'a', 'f'], ['b', 'a', 'g'], ['b', 'c', 'f'], ['b', 'c', 'g'],
['b', 'd', 'f'], ['b', 'd', 'g']]
>>print choose_first('a', s1,s2,s3)
[['a', 'c', 'f'], ['a', 'c', 'g'], ['a', 'd', 'f'], ['a', 'd', 'g']]
(and hopefully not rely on
recursion
Easy exercise of transforming recursion to iteration left to the
Raymond

Oct 26 '07 #4
Easy exercise of transforming recursion to iteration left to the
Ack! That part was already done.
Raymond
Oct 26 '07 #5
On Oct 26, 2:33 am, Raymond Hettinger <pyt...@rcn.comwrote:
On Oct 25, 8:31 am, happyhon...@gmail.com wrote:
I've got a little issue, both programming and performance-wise. I have
a set, containing objects that refer to other sets. For example, in a
simple notation: (<a, b, c>, <d, e>) (or in a more object-like
display: set(obj1.choices=set(a, b, c) ). There may be obj1..objN
objects in the outer set, and the amount of items in the choices sets
could also reach a high number. The objects in the choices sets might
overlap.
Now I want to have all possible combinations, like this: (a, d), (b,
d), (c, d), (a, e), (b, e), (c, e).
However, I've got a few catches that make an already (icky) recursive
function worse to use.
First of all, I want to be able to only choose things so that the
outer 'result sets' have the same length. For example, if you'd have
(<a, b>, <a, c>), you might pick (a, a) with a simple algorythm, the
basic behaviour of sets reducing it to (a) and thus having an improper
length. I could add yet another loop after calculating everything to
throw out any result sets with the improper length, but that would be
highly inefficient.
Second, I'd hope to be able to say that objX should be assumed to have
made the choice z. In the first example I mentioned, if I said that
'obj1 == a', the only result sets that would come out would be (a, d)
and (a, e).

def cross_nodups(*args):
'Cross product after eliminating repeat elements, keeping constant
size'
ans = [[]]
for arg in args:
ans = [x+[y] for x in ans for y in arg if y not in x]
return ans

def choose_first(obj1, *args):
'Assume a choice of a first object'
return cross_nodups(obj1, *args[1:])
>print cross_nodups('ab', 'acd', 'fg')

[['a', 'c', 'f'], ['a', 'c', 'g'], ['a', 'd', 'f'], ['a', 'd', 'g'],
['b', 'a', 'f'], ['b', 'a', 'g'], ['b', 'c', 'f'], ['b', 'c', 'g'],
['b', 'd', 'f'], ['b', 'd', 'g']]
>print choose_first('a', s1,s2,s3)

[['a', 'c', 'f'], ['a', 'c', 'g'], ['a', 'd', 'f'], ['a', 'd', 'g']]
(and hopefully not rely on
recursion

Easy exercise of transforming recursion to iteration left to the

Raymond
Wonderful, thank you Raymond!

I only had one problem with it still (damn I'm picky) and despite
prodding around in that generator expression which absolutely defies
my logic, I've been able to get it working.

In my situation, the choices are always sets rather than strings.
While it shouldn't make a difference (both are iterable), my sets
contain strings.. which end up being cut in pieces and matched
seperately with everything. I've solved this as follows:

def cross_nodups(*args):
'Cross product after eliminating repeat elements, keeping constant
size'
ans = [[]]
for arg in args:
ans = [x+[y] for x in ans for y in arg if y not in x]
return ans

def choose_first(obj1, *args):
'Assume a choice of a first object'
return cross_nodups(frozenset((obj1,)), *args[1:])

Gives results:
>>choose_first("H", set(["H", "R"]), set(["H", "R", "K", "S"]), set(["H", "R", "K", "S"]))
set([frozenset(['H', 'S', 'R']), frozenset(['H', 'K', 'R']),
frozenset(['H', 'K', 'S'])])
>>choose_first("HA", set(["HA", "RA"]), set(["HA", "RA", "KA", "SA"]), set(["HA", "RA", "KA", "SA"]))
set([frozenset(['KA', 'HA', 'RA']), frozenset(['SA', 'HA', 'RA']),
frozenset(['KA', 'HA', 'SA'])])

rather than
>>choose_first("HA", set(["HA", "RA"]), set(["HA", "RA", "KA", "SA"]), set(["HA", "RA", "KA", "SA"]))
set([frozenset(['A', 'SA', 'HA']), frozenset(['H', 'KA', 'SA']),
frozenset(['H', 'KA', 'RA']), frozenset(['A', 'KA', 'HA']),
frozenset(['H', 'HA', 'RA']), frozenset(['H', 'SA', 'HA']),
frozenset(['A', 'SA', 'RA']), frozenset(['A', 'KA', 'SA']),
frozenset(['A', 'HA', 'RA']), frozenset(['H', 'KA', 'HA']),
frozenset(['H', 'SA', 'RA']), frozenset(['A', 'KA', 'RA'])])

Now, this works great! Although I am still torn apart on a possible
optimization (that I'm not sure is an optimization yet):

- should I use the original cross_nodups() function you thought up and
convert all of its contents to a proper set of sets (a secondary loop
afterwards). This seems more efficient since I would not be doing a
lot of frozenset() and list() conversions while looping.
- however, the list() and frozenset() construct should reduce looping
quite a bit and essentially prevent a lot of iterations that would be
created due to the doubles in the original functions output.

Of course that depends on the contents, so for simplicities sake, say
that the algorythm is to run with 5-10 choices to make, each choice
being out of averaged 6 items that may or may not conflict with other
items.

Again, thank you very much Raymond, your snippet makes my monstrosity

Oct 26 '07 #6
def cross_nodups(*args):
'Cross product after eliminating repeat elements, keeping constant
size'
ans = [[]]
for arg in args:
ans = [x+[y] for x in ans for y in arg if y not in x]
return ans

def choose_first(obj1, *args):
'Assume a choice of a first object'
return cross_nodups(frozenset((obj1,)), *args[1:])
Oops, crap, I pasted the unchanged cross_nodups() you wrote. My

def cross_nodups(*args):
'Cross product after eliminating repeat elements, keeping constant
size'
ans = [[]]
for arg in args:
ans = [frozenset(list(x)+[y]) for x in ans for y in arg if y
not in x]
return set(ans)

Anyhow, thank you! :)

Oct 26 '07 #7

This thread has been closed and replies have been disabled. Please start a new discussion.

### Similar topics

 17 by: Gordon Williams | last post by: Hi, I have to lists that I need to find the common numbers (2nd rounded to nearest integral) and I am wondering if there is a more efficient way of doing it. >>> a= >>> b= >>> ... 10 by: Bulba! | last post by: Hello everyone, I'm reading the rows from a CSV file. csv.DictReader puts those rows into dictionaries. The actual files contain old and new translations of software strings. The dictionary... 1 by: Building Blocks | last post by: Hi, All I need is a simle calculate form script which contains this: A script that can handle text input, radio buttons, checkboxes, and dropdowns. Each one of these variables will contain a... 1 by: Amit | last post by: Hi, I am trying to do the following: I have two sets of integers(both are disjoint). Based on some criteria, I choose one integer from each set and do one computationally expensive operation using... 2 by: jmdeschamps | last post by: Working with several thousand tagged items on a Tkinter Canvas, I want to change different configurations of objects having a certain group of tags. I've used the sets module, on the tuple... 3 by: David MacKay | last post by: Dear Greater Py, I am writing a command-line reader for python. I'm trying to write something with the same brevity as perl's one-liner ... 9 by: SMB | last post by: I have two lists of data like the following: LIST1 , ] LIST2 , 'label': 'First Name', 'width': 0L, 'separator': ',', 'height': 0L, 'type': 2L, 'order': 1L}, {'code': 14L, 'name': 'Last... 5 by: kux | last post by: Hello everyone, I hope someone is out here who can help me with a simple calculation... I have a sales data base in access with monthly sales history by product. to make future predictions I... 4 by: Luna Moon | last post by: seeking highly efficient caches scheme for demanding engineering computing? HI all, To same the time of costly function evaluation, I want to explore the possibility of caching. Suppose in... 0 by: lllomh | last post by: Define the method first this.state = { buttonBackgroundColor: 'green', isBlinking: false, // A new status is added to identify whether the button is blinking or not } autoStart=()=>{ 0 by: Aliciasmith | last post by: In an age dominated by smartphones, having a mobile app for your business is no longer an option; it's a necessity. Whether you're a startup or an established enterprise, finding the right mobile app... 0 by: tracyyun | last post by: Hello everyone, I have a question and would like some advice on network connectivity. I have one computer connected to my router via WiFi, but I have two other computers that I want to be able to... 4 by: NeoPa | last post by: Hello everyone. I find myself stuck trying to find the VBA way to get Access to create a PDF of the currently-selected (and open) object (Form or Report). I know it can be done by selecting :... 3 by: NeoPa | last post by: Introduction For this article I'll be using a very simple database which has Form (clsForm) & Report (clsReport) classes that simply handle making the calling Form invisible until the Form, or all... 1 by: Teri B | last post by: Hi, I have created a sub-form Roles. In my course form the user selects the roles assigned to the course. 0ne-to-many. One course many roles. Then I created a report based on the Course form and... 3 by: nia12 | last post by: Hi there, I am very new to Access so apologies if any of this is obvious/not clear. I am creating a data collection tool for health care employees to complete. It consists of a number of... 0 by: isladogs | last post by: The next online meeting of the Access Europe User Group will be on Wednesday 6 Dec 2023 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, Mike... 4 by: GKJR | last post by: Does anyone have a recommendation to build a standalone application to replace an Access database? I have my bookkeeping software I developed in Access that I would like to make available to other...