Iterating Lists in Python, Ruby, Haskell (or whatever)

Update: I realize that I put the question very badly. Here's a second run.

Consider the following function:

myList = []
optimumList = []

def findOptimumListItems():
    n = 5

    for i in range (n + 1):
        for j in range (n + 1 - i):
            myList.append((i, j, n-i-j))

    for开发者_开发百科 i in myList:
        win = 0.0
        draw = 0.0
        for j in myList:
            score = 0
            if (i[0] > j[0]):
                score += 1
            if (i[0] == j[0]):
                score += 0.5
            if (i[1] > j[1]):
                score += 1
            if (i[1] == j[1]):
                score += 0.5
            if (i[2] > j[2]):
                score += 1
            if (i[2] == j[2]):
                score += 0.5  
            if (score == 2):
                win += 1
            if (score == 1.5):
                draw += 1
        if (win/(len(myList)-win-draw) > 1.0):
            optimumList.append(i)

    return optimumList

First I make a list. For n = 5 the generated list is:

[(0, 0, 5), (0, 1, 4), (0, 2, 3), (0, 3, 2), (0, 4, 1),
 (0, 5, 0), (1, 0, 4), (1, 1, 3), (1, 2, 2), (1, 3, 1),
 (1, 4, 0), (2, 0, 3), (2, 1, 2), (2, 2, 1), (2, 3, 0),
 (3, 0, 2), (3, 1, 1), (3, 2, 0), (4, 0, 1), (4, 1, 0),
 (5, 0, 0)]

Then, the function takes each element of the list and compares it with the list itself. This is how you do it: Say I'm comparing [0, 0, 5] against [3, 1, 1]. 0 loses to 3 (so no points), 0 loses to 1, so no points, 5 wins against 1 (1 point for that). A draw gets 0.5 points, a win gets 1 point. For any item, if wins are more than loses then that item is considered optimum and is added to the optimum list.

For n = 5, the optimum list is:

[(0, 2, 3), (0, 3, 2), (1, 1, 3), (1, 2, 2), (1, 3, 1), (2, 0, 3),
 (2, 1, 2), (2, 2, 1), (2, 3, 0), (3, 0, 2), (3, 1, 1), (3, 2, 0)]

My question is: How can I write the above function in a concise way? I'm especially interested in functional algorithms. Python, Ruby, Java, Haskell answers will be appreciated. (Having said that, if you have a neat solution in any language; that's okay.)

Sorry for repeating the same question. I agree that the original question was messy and hard to understand. I hope it's clear now.

Update (upon rampion's comment): Is there an efficient algorithm for this (or this type) problem?

Second Update: Great -- now I understand exactly what you want. This does the same thing as the code in your most recent edit:

def optimize(myList):
    score_tup = lambda tup_a, tup_b: sum(1.0 if a > b else 0.5 if a == b else 0 for a, b in zip(tup_a, tup_b))
    scores = ((tup_a, [score_tup(tup_a, tup_b) for tup_b in myList]) for tup_a in myList)
    scores = ((tup, score.count(2), score.count(1.5)) for tup, score in scores)
    return [tup for tup, win, draw in scores if (win * 1.0 / (len(myList) - win - draw)) > 1.0]

a = 5
myList = [(i, j, a-i-j) for i in range(a + 1) for j in range(a + 1 - i)]
print myList
print optimize(myList)

If you want to see previous versions of this answer, check the edits; this was getting too long.

in Haskell:

optimize :: Int -> [(Int,Int,Int)]
optimize n = filter optimal [ (a,b,c) | a <- [0..n], b <- [0..(n-a)], let c = n - a - b ]
  where optimal x = (>0) . sum $ map (comp x) xs
        comp (a,b,c) (a',b',c') = signum $ vs a a' + vs b b' + vs c c'
        vs x x' = case compare x x' of
                    GT -> 1
                    EQ -> 0
                    LT -> -1

Though this is fairly concise, it's not very efficient (we compare (0,3,2) with (0,2,3) and vice versa, when we only need to do that once).

This isn't done yet, but it's a good start, I think.

It's written in Ruby.

>> l = [1,2,3]
>> l.map {|n| l.map{|i| i > n ? 1 : 0.5 }}.flatten.inject(0){|start, n| start + n}
=> 6.0

What is this for? Comparing each item in the list with every other item in the list will take an extremely large time ( O(n^2), I believe), especially as the list grows in size. If you give us some context, we may be able to tell you a better way to do this.

Anyway, here's what I came up with for comparing all of your items:

>>> for i in range(len(myList)):
...     for x in range(len(myList)):
...             if x != i:
...                     if myList[i][0] > myList[x][0]:
...                             score += 1
...                     if myList[i][0] < myList[x][0]:
...                             score += .5
... 

Untested, as it never finished running, so there may be a mistake.

If I'm doing this correctly the comparison function is non-transformative, and what is returned is the same list you had before the comparison. That being said my functional program for generating the list is

def triple_tuple_generator(a):
    """Given an integer 'a', returns a generator of triple tuples of length 'a(a-1), where the tuple values are over the range 'a-1=i' (i,i-1,a-2*i+1)."""
    for i in range(a):
        for j in range(a-1):
            yield (i,j,a-1-i-j)

This is a generator so consume as you wish. If I was good enough at working with summations I would prove my hunch, but I'm a physicist not a mathematician. ;) Let me know if I got this right.