iterating through a strange tree structure?

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

>-)
Posts: 527
Joined: Tue Apr 24, 2012 1:10 am UTC

iterating through a strange tree structure?

Postby >-) » Mon Dec 30, 2013 8:02 am UTC

Given a few numbers and operators, and assuming the numbers cannot be used but the operators can, i wish to find every possible result from combining the numbers and the (two-argument) functions.

i came up with this at first

Code: Select all

for i in xrange(0,len(nums)-1):
    for j,k in itertools.combinations(nums,2):
        for op in oplist:
            nums.remove(j)
            nums.remove(k)
            nums.append(op(j,k))

but of course it won't work because i was modifying nums

then i tried this which still doesn't work for the same problem

Code: Select all

#4 numbers in nums
for a, b, in itertools.combinations(nums,2):
    for op1 in oplist:
        nums.remove(a)
        nums.remove(b)
        nums.append(op1(a,b)) #3 numbers in list
        for c, d, in itertools.combinations(nums,2):
            for op2 in oplist:
                nums.remove(d)
                nums.remove(c)
                nums.append(op2(d,c) #2 in list
                for e, f in itertools.combinations(nums,2):#there is only one possible combination.
                    for op3 in oplist:
                        nums.remove(e)
                        nums.remove(f)
                        nums.append(op3(e,f))#1 in list


and is also completely impractical if i have something like 20 numbers

the problem is that by removing and appending values to nums, i change it so that the next loop will encounter the wrong list of numbers. i can duplicate nums, but it seems wherever i do so will change nothing.

what is the typical way of iterating like this?

User avatar
Lopsidation
Posts: 183
Joined: Tue Oct 27, 2009 11:29 pm UTC

Re: iterating through a strange tree structure?

Postby Lopsidation » Mon Dec 30, 2013 10:00 pm UTC

Duplicating nums before you start changing it is the normal way to go, I think.

i can duplicate nums, but it seems wherever i do so will change nothing.

Hmm, maybe you have a copy/reference bug?

Code: Select all

a = [1,2,3]
b = a
a[0] = 6
print b[0] # prints 6

>-)
Posts: 527
Joined: Tue Apr 24, 2012 1:10 am UTC

Re: iterating through a strange tree structure?

Postby >-) » Tue Dec 31, 2013 3:40 am UTC

i worded that badly

what i meant was, if i tried something like this:

Code: Select all

numstor = [nums]+[None]*(nums-2)
for i in xrange(1,len(nums)):
    for j,k in itertools.combinations(nums,2):
        for op in oplist:
            numstor[i] = numstor[i-1][:]
            numstor[i].remove(j)
            numstor[i].remove(k)
            numstore[i].append(op(j,k))


using numstor to store the lists of numbers (for example, numstor[0] would have the original list, numstor[1] would have one less element, and so on

the algorithm fails because it runs "breadth first" rather than "depth first" (if i even used those terms correctly. Instead of taking numstor[1] and removing another element to make numstor[2], the algorithm finds the next numstor[1] instead, deleting the one currently there. I'm not sure how to restructure my code so it works right.

User avatar
Xanthir
My HERO!!!
Posts: 5410
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: iterating through a strange tree structure?

Postby Xanthir » Tue Dec 31, 2013 8:21 am UTC

Don't try to build the tree from the top down, do it from the bottom up.

Start with the most basic expressions possible - a single number with no ops. For each of your starting numbers, produce a (result, remaining_nums) tuple. These are your starting cases.

Then, for each of them, cycle through the remaining_nums, producing new (result, remaining_nums) tuples for the results of combining each previous result with the num you're cycling through. Repeat.

Something like this (completely untested, treat it as pseudocode):

Code: Select all

original_nums = set(...)
ops = [...]
all_results = []
results = [(num, original_nums.difference([num])) for num in original_nums]
all_results.extend(results)
new_results = []
for i in range(2, len(original_nums)):
    for val, more_nums in results:
        for num in more_nums:
            less_nums = more_nums.difference([num])
            for op in ops:
                new_results.append((op(val, num), less_nums))
    all_results.extend(new_results)
    results, new_results = new_results, []
all_results = [result[0] for result in all_results]


The end result should be a list of values produced by all possible constructions.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

>-)
Posts: 527
Joined: Tue Apr 24, 2012 1:10 am UTC

Re: iterating through a strange tree structure?

Postby >-) » Thu Jan 02, 2014 7:58 pm UTC

neat solution, i just managed to wrap my head around it. thanks!


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 8 guests