Algorytm - trójkąt Pascala - znalezienie powtórzeń

[Gieneq]

Dla szukających wrażeń 🙂 Może komuś uda się przygotować lepsze rozwiązanie.

Zadanie polega na wyznaczeniu liczb z trójkąta Pascala takich, że w zadanej liczbie warstw piramidy row_limit, liczba występują więcej niż 3 razy. Próbowałem w oparciu o liczby Fibonacciego i inną teorię z materiałów, ale naiwne zbudowanie całej piramidy i policzenie wystąpień dalej jest najszybszym algorytmem.

Treść zadania:

Przydatne linki:

https://medium.com/@duhroach/fast-fun-with-pascals-triangle-6030e15dced0

https://en.wikipedia.org/wiki/Singmaster's_conjecture

Mój kod:

def search_pascal_multiples_slow(row_limit):
    # dla 2000 - 1210ms
    numbers_bag = []
    pyramid = [[1, 3, 3, 1]]

    for row_idx in range(1, row_limit-2):
        rows_numbers = list()
        rows_numbers.append(1)
        previous_row = pyramid[row_idx - 1]
        for el_idx in range(1, row_idx):
            rows_numbers.append(previous_row[el_idx - 1] + previous_row[el_idx])
        rows_numbers.append(1)

        pyramid.append(rows_numbers)
        numbers_bag.extend(rows_numbers[2:-2])

    return sorted([key for key, value in Counter(numbers_bag).items() if value > 3])

 

[H1M4W4R1]

def pascal_triangle(n):
    if n == 1:
        return [[1]]
    elif n == 2:
        return [[1], [1, 1]]
    else:
        triangle = [[1], [1, 1]]
        for i in range(2, n):
            row = [1]
            for j in range(1, i):
                row.append(triangle[i-1][j-1] + triangle[i-1][j])
            row.append(1)
            triangle.append(row)
        return triangle

? 😉 

EDIT: czytać nie umiem xD

Edytowano Listopad 8, 2021 przez H1M4W4R1

[Gieneq]

@H1M4W4R1 dobra działa, tam jeszcze trzeba policzyć elementy, ale i tak jest poprawa. Tylko pytanie czy tego nie robi się bardziej algebraicznie? 

[H1M4W4R1]

2 minuty temu, Gieneq napisał:

@H1M4W4R1 dobra działa, tam jeszcze trzeba policzyć elementy, ale i tak jest poprawa. Tylko pytanie czy tego nie robi się bardziej algebraicznie? 

def pascal_triangle(max_row):
    """
    Prints the pascal triangle up to max_row
    """
    row = [1]
    for i in range(max_row):
        row = [1] + [row[x] + row[x+1] for x in range(len(row)-1)] + [1]

To masz na myśli? 😄 

[Polecacz 101]

Produkcja i montaż PCB - wybierz sprawdzone PCBWay!
   • Darmowe płytki dla studentów i projektów non-profit
   • Tylko 5$ za 10 prototypów PCB w 24 godziny
   • Usługa projektowania PCB na zlecenie
   • Montaż PCB od 30$ + bezpłatna dostawa i szablony
   • Darmowe narzędzie do podglądu plików Gerber
Zobacz również » Film z fabryki PCBWay

[Gieneq]

@H1M4W4R1 fajnie wygląda, składanie list czyni cuda 🙂 

Dostosowałem do zadania, rozwiązanie dla 250 jest poprawne:

def pascal_triangle_row(max_row):
    row = [1]
    for i in range(max_row):
        row = [1] + [row[x] + row[x+1] for x in range(len(row)-1)] + [1]
    return row[2:-2]

# print(pascal_triangle_row(8))

def search_pascal_multiples_slow_v2(row_limit):
    # dla 2000 - 1210ms
    numbers_bag = []
    for row_idx in range(4, row_limit):
        numbers_bag.extend(pascal_triangle_row(row_idx))

    return sorted([key for key, value in Counter(numbers_bag).items() if value > 3])

Można na pewno darować sobie jedynkę i przedostatni element i w ogóle policzyć tylko połowę piramidy, ale ta metoda niestety działa ponad 40 razy wolniej 😞 

Calculating 250 took: 247.402 ms.
[120, 210, 1540, 3003, 7140, 11628, 24310, 61218182743304701891431482520]

Tu masz wynik tego co wrzuciłem na początku:

Calculating 250 took: 7.025 ms.
[120, 210, 1540, 3003, 7140, 11628, 24310, 61218182743304701891431482520]

Także myślimy dalej 😉 Wydaje mi się że to już nie jest kwestia lepszego ułożenia iteracji tylko algorytmiki.

BTW. próbowałem z numpy i metodą pascla i było bardzo źle.

Edytowano Listopad 8, 2021 przez Gieneq

[H1M4W4R1]

Przerzuciłem się na C#, bo dla mnie jest ciut wygodniejszy niż Python 😉 

public static BigInteger[] NextTriangleRow(BigInteger[] row, int n)
        {
            var newRow = new BigInteger[row.Length + 1];
            newRow[0] = newRow[^1] = row[0] + n;
            for (var i = 1; i < newRow.Length - 1; i++)
                newRow[i] = row[i - 1] + row[i];
            return newRow;
        }

Jedyna opcja optymalizacji to wersja ekonomiczna copy-paste. Jest o ok. 25% szybsze od mojej poprzedniej wersji.

public static BigInteger[] NextTriangleRow(BigInteger[] row, int n)
        {
            var newRow = new BigInteger[row.Length + 1];
            newRow[0] = newRow[^1] = row[0] + n;

            for (var i = 1; i < newRow.Length / 2 + 1; i++)            
                newRow[^(i + 1)] = newRow[i] = row[i - 1] + row[i];
            
            return newRow;
        }

Z tym, że trzeba zaczynać od "[10, 10]" (w trójkącie: 1, 5, 10, 10, 5, 1). Szóstka i tak nie wystąpi więcej niż raz (bo jest odcinana 😉 ) [Kolejne 15% do szybkości]

Btw. chyba można zacząć od 

var row = new BigInteger[] {36, 84, 126, 126, 84, 36};

Ale to tylko teoria, a o tej porze ciut za późno na liczenie 😄 

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Numerics;
using System.Threading.Tasks;
using Newtonsoft.Json;

namespace Pascal
{
    class Program
    {

        public static List<BigInteger> CountOccurences(int maxRow)
        {
            var occurences = new Dictionary<BigInteger, short>();
            
            var row = new BigInteger[] {36, 84, 126, 126, 84, 36};
            for (var q = 9; q < maxRow + 2; q++)
            {
                row = NextTriangleRow(row, q);
      
                foreach (var v in row)
                {
                    if (v <= q) continue;

                    if (occurences.ContainsKey(v))
                        occurences[v]++;
                    else
                        occurences.Add(v, 1);
                }
            }

            return occurences.Where(k => k.Value > 3).Select(k => k.Key).ToList();
        }

        public static BigInteger[] NextTriangleRow(BigInteger[] row, int n)
        {
            var newRow = new BigInteger[row.Length + 1];
            newRow[0] = newRow[^1] = row[0] + n;

            for (var i = 1; i < newRow.Length / 2 + 1; i++)
            {
                newRow[^(i + 1)] = newRow[i] = row[i - 1] + row[i];
            }

            return newRow;
        }


        static void Main(string[] args)
        {
            var sw = new Stopwatch();
            sw.Start();
            var row = CountOccurences(250);
            sw.Stop();
            Console.WriteLine(sw.ElapsedMilliseconds + "ms");
            
            foreach (var v in row)
                Console.Write(v + " ");
            Console.WriteLine();
            
            Console.WriteLine("");
        }
    }
}

 

Edytowano Listopad 9, 2021 przez H1M4W4R1

[Gieneq]

@H1M4W4R1 dziękuję za zaangażowanie 🙂 ale coś mnie jednak korci, żeby spróbować ulepić coś z tego. W pakiecie scipy są 2 funkcje do wyznaczania wartosci symbolu Newtona i coś mi się wydaje, że gdyby odnieść się do tego, to można by sprawnie wyznaczyć te liczby:

Też robiłem podejście do obiektów typu Fraction gdzie jest informacja o liczniku i mianowniku dzielenia, działania na tych obiektach są chyba 3x wolniejsze od floatów ale w jednym z algorytmów do wyznaczania wartości pascal(row, col) występuje dzielenie, któe po zaokrągleniu tworzy niejednoznaczne rozwiązania 😞 

[Gieneq]

Dobra... nie mam pomysłu 😄 

Dorzuciłem drobną optymalizację - zauważyłem że połowę czasu zabiera policzenie elementów. Podobno w Pythonie nie znajdę nic lepszego od collections.Count więc nawet nie próbowałem szukać rozwiązań w numpy. Poza tym:

1. zauważyłem, że piramida jest symetryczna 🤦‍♂️ więc wystarczy wyznaczyć połowę i to najwyraźniej bez środkowego elementu w warstwach nieparzystej długości (w teorii nikt nie roztrząsa tematu nieparzystych powtórzeń). Zadanie sprowadza się do znalezienia elementów które występują więcej niż 1 raz.
2. druga optymalizacja to liczba elementów piramidy potrzebnych do wyznaczenia połowy ostatniej warstwy - będzie to min(index, floor(limit/2)).

Pierwsza optymalizacja skutkowała redukcją czasu wykonania z 900 na 700 ms. Druga ujęła kolejne około 100 ms. Dodałem jeszcze składanie list i czas wykonania dla 2000 wynosi tylko 520-550 ms 🥳 Nie wiem czy da się lepiej, kto ma pomysł niech walczy.

from collections import Counter
import time

def search_pascal_multiples_faster_v2(row_limit):
    numbers_bag = []
    pyramid = [[1, 4, 6, 4, 1]]
    # for i in range(5):
    #     print(i, ": -", sep="")

    for row_idx in range(1, row_limit-4):
        previous_row = pyramid[row_idx - 1]
        rows_numbers = [previous_row[el_idx - 1] + previous_row[el_idx] for el_idx in range(1, min(row_idx+4, row_limit//2))]

        pyramid.append([1] + rows_numbers + [1])
        numbers_bag.extend(rows_numbers[1:2+row_idx//2])
        # print(row_idx+4, rows_numbers, rows_numbers[2:3+row_idx//2], sep=": ")

    return sorted([key for key, value in Counter(numbers_bag).items() if value > 1])

if __name__ == '__main__':
    nums_limit = 2000
    starting_time = time.time_ns()
    output = search_pascal_multiples_faster_v2(nums_limit) # 7ms
    ending_time = time.time_ns()

    print(f"Calculating {nums_limit} took: {round((ending_time - starting_time) * 10 ** -6, 3)} ms.")
    print(output)

Wyszło:

Calculating 2000 took: 525.617 ms.
[120, 210, 1540, 3003, 7140, 11628, 24310, 61218182743304701891431482520, 3537835171522765057006983148520718494957187357011427136691375227388082606684583032666088334962061461901090477513197821330000906170565587040820236444389470701575515092325417606033095416151914090271577807800]

 

[H1M4W4R1]

25 minut temu, Gieneq napisał:

druga optymalizacja to liczba elementów piramidy potrzebnych do wyznaczenia połowy ostatniej warstwy - będzie to min(index, floor(limit/2))

Możesz jeszcze wyciąć dwie graniczne liczby z lewej i prawej, patrz mój algorytm je pomija co daje dodatkowe kilkanaście procent dla 250

9 godzin temu, H1M4W4R1 napisał:

public static BigInteger[] NextTriangleRow(BigInteger[] row, int n) { var newRow = new BigInteger[row.Length + 1]; newRow[0] = newRow[^1] = row[0] + n; for (var i = 1; i < newRow.Length / 2 + 1; i++) newRow[^(i + 1)] = newRow[i] = row[i - 1] + row[i]; return newRow; }

Patrz tutaj 😉 

EDIT: jeszcze można usunąć dzielenie wiersza na pół, bo ilość elementów rośnie liniowo 😉 Co dwa wiersze wartość maksymalna dla "i" będzie rosła o 1 😉 

Edytowano Listopad 9, 2021 przez H1M4W4R1