Listenin permutasyonlarini siralama

aib · Mart 10, 2020, 9:14ös

Goruyorum ki bu aralar kombinasyon/permutasyon/secilim sorulari baya ragbet goruyor. Kimilerine tek satirlik recursive lambda olarak verdigim cevaplar da ilgi cekiyor. O zaman basitlerinden bir tanesini egzersiz olarak yapalim: Listenin permutasyonlari.

Evet, itertools.permutations'in tek parametreli versiyonunu yaziyoruz:

>>> list(per("abcd"))
[('a', 'b', 'c', 'd'), ('a', 'b', 'd', 'c'), ('a', 'c', 'b', 'd'), ('a', 'c', 'd', 'b'), ('a', 'd', 'b', 'c'), ('a', 'd', 'c', 'b'), ('b', 'a', 'c', 'd'), ('b', 'a', 'd', 'c'), ('b', 'c', 'a', 'd'), ('b', 'c', 'd', 'a'), ('b', 'd', 'a', 'c'), ('b', 'd', 'c', 'a'), ('c', 'a', 'b', 'd'), ('c', 'a', 'd', 'b'), ('c', 'b', 'a', 'd'), ('c', 'b', 'd', 'a'), ('c', 'd', 'a', 'b'), ('c', 'd', 'b', 'a'), ('d', 'a', 'b', 'c'), ('d', 'a', 'c', 'b'), ('d', 'b', 'a', 'c'), ('d', 'b', 'c', 'a'), ('d', 'c', 'a', 'b'), ('d', 'c', 'b', 'a')]

Hatta Python’da yazarsaniz sunlari test case olarak kullanabilirsiniz:

import itertools
assert sorted(per([]))            == sorted(itertools.permutations([]))
assert sorted(per([1,2]))         == sorted(itertools.permutations([1,2]))
assert sorted(per(['x','y','z'])) == sorted(itertools.permutations(['x','y','z']))
assert sorted(per("ABCD"))        == sorted(itertools.permutations("ABCD"))
assert sorted(per([1,2,3,4,5]))   == sorted(itertools.permutations([1,2,3,4,5]))

Recursive (ozyinelemeli) fonksiyonlari anlamak, yazabilmek isteyenler var. O zaman:

Bonus 1: Loop, yani for veya while kullanmadan yazin. (*list comprehension icindeki for kullanilabilir ama sart veya gerekli degil.)
Bonus 2: Degisken kullanmadan yazin. (Parametreler, for x in xs'deki x filan kullanilabilir. Tekrari onlemek icin x = uzun_cagri(y, z, w) bile tamam. Bilgi biriktiren, yeni degerini eskisinden alan degisken istemiyoruz: x = x + 1 veya x.append(...) gibi.)

aib · Mart 10, 2020, 9:21ös

Bu arada simdi dusundum de, recursion’in nasil olacagi cok bariz degil. Neyse, olmadi baska bir problem buluruz.

Orhan61 · Mart 12, 2020, 11:11öö

Ben itertools modülünü keşfetmeden önce permütasyon ,kombinasyon üzerine düşünmüştüm ama işin içinden çıkamamıştım.Bu tür sorular için itertools büyük bir nimet gerçektende
Ayrıca bu tür sorulara kafa yormak zevk veriyor keşke özyineleme konusuna sizin kadar vakıf olabilsem çıkacak sonucu öngöremiyorum nedense bir püf noktası filan varmı merak içindeyim
Sorunun çözümü üzerine kafa yorucam sonuçta bu özyinelemeyi öğrenmem gerekli

toxide · Mart 12, 2020, 1:50ös

Tek satırda mı yazacağız per() özyinelemeli fonksiyonunu yoksa bir kısıtlama yok mu?

Bir de burada ne demek istediğinizi anlayamadım.

EkremDincel · Mart 12, 2020, 2:42ös

Sanırım aynı fonksiyonu iki defa çağırmak yerine sonucu bir değişkene atayabilirsiniz demiş.

EkremDincel · Mart 12, 2020, 4:08ös

swaputil = lambda mutable, i, j, k, l: mutable.__setitem__(i, l) or mutable.__setitem__(j, k)
swap = lambda mutable, i, j: swaputil(mutable, i , j, mutable[i], mutable[j])


perutil = lambda iterable, lenght, l, i = 0: [(swap(iterable, i, j) or perutil(iterable, lenght, l, i + 1) or swap(iterable, i, j)) for j in range(i, lenght)] and 0 \
          if i < lenght \
          else l.append(tuple(iterable)) # sadece itertools.permutations ile aynı olması için tuple ekliyoruz

per = lambda iterable, l: perutil(list(iterable), len(iterable), l) or l
permutations = lambda iterable: per(iterable, [])


if __name__ == "__main__":
    import itertools
    assert sorted(permutations([]))            == sorted(itertools.permutations([]))
    assert sorted(permutations([1,2]))         == sorted(itertools.permutations([1,2]))
    assert sorted(permutations(['x','y','z'])) == sorted(itertools.permutations(['x','y','z']))
    assert sorted(permutations("ABCD"))        == sorted(itertools.permutations("ABCD"))
    assert sorted(permutations([1,2,3,4,5]))   == sorted(itertools.permutations([1,2,3,4,5]))`

Emerald_Gamer · Mart 12, 2020, 7:59ös

Yukarda per(“ABCD”) fonksiyonunun çıktı uzunluğu argüman uzunluğunun faktoriali degil mı?

Orhan61 · Mart 12, 2020, 8:27ös

permütastonlarda P(n,n) =n! dir.

aib · Mart 12, 2020, 11:02ös

Puf noktasi su: Ozyinelemeli fonksiyonlar girdiye gore iki turlu davraniyor: Base case (girdiye gore direkt cikti) ve recursive case (ozyinelemenin dondurdugu deger uzerinden cikti).

Faktoryel yazdiniz mi mesela? Recursion icin ilk verilen ornektir ama atlanabiliyor. (Base case n=0, recursive case n>0.)

Ikinci ornek icin bir sayi listesinin toplamini alan bir fonksiyon onerebilirim.
Veya carpimini, veya minimumunu, veya maksimumunu. (Monoid uzerinden fold’mus aslinda bunlar, ama bunu recursive fonksiyon yazabilmeye basladiktan 15 sene sonra ogrendim :).)

Denemeniz lazim. Dusunce adimlarinizi burada paylasirsaniz elimden geldigince yardim etmeye calisirim, ve eminim bu amacta yalniz kalmam.

Orhan61 · Mart 13, 2020, 8:41öö

şunu söyleyebilirim ki aşağıdaki linkteki örneklerin bir çoğunu kendim yazdım yazamadıklarımıda sonradan okuyunca anladım
fibonanci faktöriyel max min bunlar kolay ve rahatlıkla öngerebildiklerim bunlarda sıkıntı yaşamadım

https://nihil.ceng.metu.edu.tr/opc/pcourse/4/

Orhan61 · Mart 13, 2020, 8:51öö

kendime göre orta seviye olarak şu örneği(PASCAL ÜÇGENİNİN N.Cİ SATIRINI VERİR)

    if n == 1:
        return [1]
    else:
        SAT = [1]
        ON_SAT = pascal(n-1)
        for i in range(len(ON_SAT)-1):
            SAT.append(ON_SAT[i] + ON_SAT[i+1])
        SAT += [1]
    return SAT
for i in range(1,11):
    print(pascal(i))
ORTA ÜSTÜ OLARAK  (ALT KÜMELERİ VERİR)
def eleman_ekleyici(eleman, liste_listesi): # liste icindeki her listeye elemani ekler

    if liste_listesi == []:

        return []

    else:

        return [liste_listesi[0] + [eleman]] + eleman_ekleyici(eleman, liste_listesi[1:])





def altKumeler(liste):

    if len(liste) == 0:

        return [[]]

    else:

        return altKumeler(liste[:-1]) + eleman_ekleyici(liste[-1], altKumeler(liste[:-1]))

# ornek

# print(sorted(altKumeler(["a","b","c"])))

# >>> [[], ['a'], ['a', 'b'], ['a', 'b', 'c'], ['a', 'c'], ['b'], ['b', 'c'], ['c']]
ZOR ÖRNEK OLARAK DA BU ÖRNEĞİ VEREBİLİRİM ( PARÇALANIŞ SAYISI)
def findCombinationsUtil(arr, index, num,reducedNum):
    if (reducedNum < 0):
        return;
    if (reducedNum == 0):

        for i in range(index):
            print(arr[i], end=" ");
        print("");
        return;
    if index == 0 :
        prev=1
    else :
        prev=arr[index - 1];
    for k in range(prev, num + 1):
        arr[index] = k;
        findCombinationsUtil(arr, index + 1, num,
                             reducedNum - k);

def findCombinations(n):
    arr = [0] * n;
    findCombinationsUtil(arr, 0, n, n);
findCombinations(20)

aib · Mart 13, 2020, 10:32öö

Cok ilginc olmus! Imperatif kodun loop yerine recursion kullanilan hali, yanlis okumadiysam?

Aradaki o or'lar side effect’li statement’lari birlestirmek icin mi? Alt alta da yazabilirdik:

def perutil(iterable, lenght, l, i = 0):
    if i < lenght:
        for j in range(i, lenght):
            swap(iterable, i, j)
            perutil(iterable, lenght, l, i + 1)
            swap(iterable, i, j)
    else:
        l.append(tuple(iterable))

aib · Mart 13, 2020, 10:56öö

Mesela bunu basitlestirelim:

Orhan61:

def pascal(n):
    if n == 1:
        return [1]
    else:
        SAT = [1]
        ON_SAT = pascal(n-1)
        for i in range(len(ON_SAT)-1):
            SAT.append(ON_SAT[i] + ON_SAT[i+1])
        SAT += [1]
    return SAT

for i in range(1,11):
    print(pascal(i))

En karmasik yer for loop’u. (Okuyarak anlamadim, calistirip bakmam gerekti ne yaptigina. + operatoru Python’da bir suru farkli is yapiyor cunku.)

i ve range kullanmamizin sebebi indise ve bir araliga ihtiyacimiz olmasi mi? Hayir, bunlar yapmak istedigimizi tane tane ifade etme aliskanligindan geliyor. Aslinda istedigimiz ardisik ciftler. itertools’a bakiyoruz:

import itertools

def pairwise(iterable):
    "s -> (s0,s1), (s1,s2), (s2, s3), ..."
    a, b = itertools.tee(iterable)
    next(b, None)
    return zip(a, b)

Kodda:

def pascal(n):
    if n == 1:
        return [1]
    else:
        SAT = [1]
        ON_SAT = pascal(n-1)
        for a, b in pairwise(ON_SAT):
            SAT.append(a + b)
        SAT += [1]
    return SAT

ON_SAT’a da ihtiyac kalmadi:

def pascal(n):
    if n == 1:
        return [1]
    else:
        SAT = [1]
        for a, b in pairwise(pascal(n-1)):
            SAT.append(a + b)
        SAT += [1]
    return SAT

Peki SAT’in hakikaten hayatina [1] olarak baslayip, yavas yavas buyumesine ihtiyacimiz var mi? Hayir, basinda ve sonunda 1 olan ve arada ciftlerin toplami olan bir liste istiyoruz:

def pascal(n):
    if n == 1:
        return [1]
    else:
        SAT = [1] + [a+b for a, b in pairwise(pascal(n-1))] + [1]
    return SAT

Degiskene de ihtiyac yok:

def pascal(n):
    if n == 1:
        return [1]
    else:
        return [1] + [a+b for a, b in pairwise(pascal(n-1))] + [1]

Birden fazla return’e de:

def pascal(n):
    return ([1]) if (n == 1) else ([1] + [a+b for a, b in pairwise(pascal(n-1))] + [1])

Sonra lambda’lastirmak istersek:

pascal = lambda n: ([1]) if (n == 1) else ([1] + [a+b for a, b in pairwise(pascal(n-1))] + [1])

aib · Mart 13, 2020, 11:09öö

Bunun sebebi bu fonksiyonlarin taniminin zaten recursive verilmesi mi?
Yoo, min/max pek de oyle sayilmaz.

Onemli olan aradaki adimi bulabilmek. Mesela P(n,n) = n! dendi ya, bunun sebebi nedir? Neden P(3,3) ile P(4,4) arasinda 4 kat buyuyor liste? Fiziksel olarak bakarsak:

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

Bunlara 4’ler nasil ekleniyor?

EkremDincel · Mart 13, 2020, 11:39öö

Evet lambda kullanmaya çalışınca böyle oluyor. Tabii algoritma ile alakalı.

Elbette, normalde öyle yapmak lazım zaten.

Orhan61 · Mart 13, 2020, 12:18ös

Anlatımınız gayet sade ve anlaşılır olmuş emeğinize sağlık böyle basamak basamak olunca anladım
Ama sizin tek satırlık kodlar beni benden alıyor

aib · Mart 13, 2020, 12:42ös

Evet, ben de side effect’li kodun imperatif stilde yazilmasi taraftariyim.

Hatta sozkonusu dil Python ise her halukarda birden fazla statement/expression/satir kullanmak lazim, yoksa okunmaz oluyor

Fonksiyonel programlamanin yan etkisi. Her program tek bir expression’a indirgenebiliyor.

Ama okunamaz olduklarinin farkindayim, evet

aib · Mart 13, 2020, 1:01ös

Ha, bu arada:

per = lambda es: [()] if len(es) == 0 else [(es[i],) + sub for i in range(len(es)) for sub in per(es[:i] + es[i+1:])]

Orhan61 · Mart 13, 2020, 6:09ös

aslında her defasında bir önceki permütasyonların hepsinin aralarına serpiyoruz son elemanı ,
3 elemanlı bir kümede 3+1 dört yere yerleşebiliyor ondan 4 le çarpıyoruz

EkremDincel · Mart 13, 2020, 7:12ös

Tanımı öyle, siz tam olarak ne demek istediniz ki?

P(x, y) = x! / (x - y)!