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

1

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

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

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

Мой вопрос: как написать описанную выше функцию в сжатом? Меня особенно интересуют функциональные алгоритмы. Ответы Python, Ruby, Java, Haskell будут оценены. (Сказав это, если у вас есть четкое решение на любом языке, это хорошо).

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

Обновление (по комментарию на рампе): Есть ли эффективный алгоритм для этой проблемы (или этого типа)?

  • 1
    Хорошо, я все еще в замешательстве. Что такое item_ , item_0 и item_n ?
  • 0
    Это было бы понятнее, если бы вы сказали такие вещи, как myList[0][0] , myList[0][1] и т. Д., Используя обычный (для Python) синтаксис вложенного списка.
Показать ещё 2 комментария
Теги:
haskell
functional-programming

5 ответов

4
Лучший ответ

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

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)

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

Поделиться
  • 0
    почему не просто: myList = [(i, j, a-1-ij) for i in range(10) for j in range(a - i)]
  • 0
    @newacct, да, я попробовал это, и это не сработало так, как я ожидал. Но я только что попробовал то, что вы напечатали, и это работает. Поэтому я, должно быть, ошибся, когда попробовал в первый раз. Я буду редактировать ...
4

в 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) и наоборот, когда нам нужно сделать это только один раз).

Поделиться
1

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

Это написано на 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
Поделиться
  • 1
    Вы также можете использовать .inject(:+) вместо .inject(0){|start, n| start += n} . (и += должно быть просто + )
  • 0
    Спасибо, я редактировал пост.
0

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

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)

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

Поделиться
0

Для чего это? Сравнение каждого элемента в списке с каждым другим элементом в списке займет очень большое время (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
...

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

Поделиться

Ещё вопросы

Сообщество Overcoder
Наверх
Меню