Итерация списков в Python, Ruby, Haskell (или что-то еще)

Question

Обновление: я понимаю, что поставил вопрос очень плохо.Вот второй прогон.

Рассмотрим следующую функцию:

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

Сначала я составлю список.Для n = 5 сгенерированный список имеет вид:

[(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)]

Затем функция берет каждый элемент списка и сравнивает его с самим списком.Вот как вы это делаете: скажем, я сравниваю [0, 0, 5] с [3, 1, 1].0 проигрывает 3 (поэтому нет очков), 0 проигрывает 1, поэтому нет очков, 5 побед против 1 (1 очко за это).За ничью 0,5 очка, за победу - 1 очко.Для любого предмета, если выигрыши больше, чем проигрыши, тогда этот предмет считается оптимальным и добавляется в оптимальный список.

Для n = 5 оптимальный список:

[(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вопрос: как я могу написать вышеупомянутую функцию в кратком способе?Меня особенно интересуют функциональные алгоритмы.Будут оценены ответы на Python, Ruby, Java, Haskell.(Сказав это, если у вас есть четкое решение на любом языке; это нормально.)

Извините за повторение того же вопроса.Я согласен, что первоначальный вопрос был запутанным и трудным для понимания.Надеюсь, теперь все ясно.

Обновление (после комментария rampion): Существует ли эффективный алгоритм для этой (или этого типа) проблемы?

Answer 1

в 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

Хотя это довольно кратко, это не очень эффективно (мы сравниваем (0,3,2) с (0,2,3) и наоборот, когда мы тольконужно сделать это один раз).

Answer 2

Второе обновление : Отлично - теперь я точно понимаю, что вы хотите.Это то же самое, что и код в вашем последнем редактировании:

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)

Если вы хотите увидеть предыдущие версии этого ответа, проверьте исправления;это становилось слишком длинным.

Answer 3

Это еще не сделано, но я думаю, это хорошее начало.

Написано на 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

Answer 4

Если я делаю это правильно, функция сравнения не преобразующая, и возвращается тот же список, который вы имели до сравнения. При этом моя функциональная программа для генерации списка -

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)

Это генератор, так что потребляйте, как вы хотите. Если бы я был достаточно хорош в работе с суммированием, я бы доказал свою догадку, но я физик, а не математик. ;) Дайте мне знать, если я правильно понял.

Answer 5

Для чего это нужно? Сравнение каждого элемента в списке с каждым другим элементом в списке займет очень много времени (я полагаю, O (n ^ 2)), особенно с учетом увеличения размера списка. Если вы дадите нам некоторый контекст, мы сможем предложить вам лучший способ сделать это.

В любом случае, вот что я придумал для сравнения всех ваших предметов:

>>> 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
... 

Не проверено, так как оно никогда не заканчивалось, поэтому может быть ошибка.