Algorytm wariacji par zbiorów bez powtórzeń.

0

Witam,
poszukuję skryptu, który z pewnego zbioru wygeneruje mi pary podzbiorów n elementowych bez powtórzeń przykład:

zbiór wyjściowy: [a,b,c,d];
generowanie par podzbiorów 1elementowych:
[a, b] [a, c] [a, d] [b, c] [b, d] [c, d]

zbiór wyjściowy: [a,b,c,d];
generowanie par podzbiorów 2elementowych:
[ab, cd] [ac, db] [ad, bc]

wyjściowy: [a,b,c,d,e,f]
generowanie 3 elementowych podzbiorów:
[abc, def] [abd, cef] [abe, cdf] [abf, cde] [acd, bef] [ace, bdf] [acf, bde] [ade, bcf] [adf, bce] [aef bcd]...

wyjściowy [a,b,c,d,e,f]
generowanie 2 elementowych podzbiorów:
[ab , cd] [ab, ce] [ab, de] [ac, bd] [ac, be] [ac, de] [ad, bc] [ad, be] [ad, ce] [ae, bc] [ae, bd], [ae, cd]...

Niestety google nic szczególnego mi nie podpowiada, może ktoś z Was próbował napisać coś w tym stylu ?

EDIT: Ogólnie staram się napisać skrypt generując mecze w fifę / PESa ale również w kombinacji 2v2 lub 3v3. Tak więc mając 4 graczy chcę wygenerować przy rozgrywkach 2v2 wszystkie kombinacje w jakich mogą zagrać - w tym wypadku będą tylko 3 kombinacje [gracz1, gracz2] vs [gracz3, gracz4] [gracz1, gracz3] vs [gracz2, gracz4] oraz [gracz1, gracz4] vs [gracz2, gracz4]

1

Pierwszy przykład robisz prosto na dwóch pętlach.

$result = [];
for($i=0;$i<$n;$i++)
{
    for($j=$i;$j<$n;$j++)
    {
        if($i!=$j) {
            array_push($result, [$set[$i], $set[$j]]);
        }
    }
}

Co do reszty, musisz odpowiednio zmodyfikować sobie kod. Zresztą można to zrobić na wiele sposobów, wyżej jest tylko przykład. Skryptów niestety nie znam, bo nigdy nie potrzebowałem, ale jestem pewien że na githubie coś znajdziesz.

Pisałem z telefonu, więc mogą być jakieś błędy.

0

@mefsh, dzięki nakierowałeś mnie, aczkolwiek teraz stoję przed problemem, jak sprawić aby zamienić zagnieżdżone pętle na funkcję, do której będe przekazywał parametr z ilością jaka ma być zagnieżdżona.
Obecnie mam takie coś:

$players = ['a', 'b', 'c', 'd', 'e', 'f'];

function getUsersTeams($players) {
    $output = [];
    for ( $i = 0; $i < count( $players ); $i++ ) {
        for ( $j = $i + 1; $j < count( $players ); $j++ ) {
            $output[] = [ $players[ $i ], $players[ $j ] ];
        }
    }

    return $output;
}

...co pięknie generuje mi 15 par, każdy z każdym, bez powtórzeń. Niestety aby sprawić aby to nie były pary tylko 3 elementy, muszę dodać kolejną pętle

for ( $k = $j + 1; $k < count( $players ); $k++ ) {
    $output[] = [ $players[ $i ], $players[ $j ], $players[ $k ] ];
}

Ma ktoś może pomysł jak to powinno wyglądać np. rekurencyjnie ?

1

Hej,
może mało algorytmicznie, ale działa... Czasem jak nie wiadomo jak wyłowić wszystkie rozwiązania, to można znaleźć je losowo... :) O ile nie jest dużo możliwości... Ale zakładam, że masz przystępne ilości drużyn... :) Sorki, za Python, ale jeżeli jesteś programistą, to wymaga to zainstalowania Pythona (wersja 3), max 5 minut... i odpalenia kodu... :)

import random

def polosujmy(lista, ile):
    n = len(lista)
    wynik = set()
    nry = list(range(n))
    for i in range(1000*n):
        random.shuffle(nry)
        a = []
        b = []
        for j in range(ile):
            a.append(nry[j])
            b.append(nry[ile+j])
        z= []
        a.sort()
        b.sort()
        x = [",".join(map(str, a)), ",".join(map(str, b))]
        x.sort()
        wynik.add(tuple(x))
    return wynik

print(polosujmy([1,2,3,4,5,6], 3))
print(polosujmy([1,2,3,4], 2))

Pozdrawiam... :)

0

@hurgadion dzięki, Twój kod działa, aczkolwiek nie wiem, czy rozumiem go na tyle by przepisać go na PHP :/ Choć szukanie losowe, jak widać się udaje, to piszę sobie to po godzinach i chciałbym aby było napisane jak najwydajniej, gdyż czas mnie nie goni :P Może ktoś ma inny, wydajniejszy / milszy pomysł na rozwiązanie tego problemu ? :)

0

zagooglałem... i chyba da się... odpal kod:

from itertools import *

def powerset(iterable, n):
    a = []
    w = []
    x = list(chain.from_iterable(combinations(iterable, r) for r in range(n, n+1)))
    for e in x:
        if e not in a:
            for f in x:
               if len(set(e).union(set(f)))==2*n:
                   w.append([e, f])
                   a.append(e)
                   a.append(f)
    return w

print(powerset([1, 2, 3, 4, 5, 6], 3))
print(powerset([1, 2, 3, 4], 2))

Pozdrawiam... :)

PS. tylko jest chyba jeden problem, jak to przełożyć na PHP... poszukaj może algorytmu na wypisywanie wszystkich kombinacji zbioru k-elementowego ze zbioru n-elementowego, powinno coś być w sieci, może nawet w PHP, a potem przerób powyższy kod... sądzę, że chyba potrafisz... :)

Dodatek (udało się bez pomocniczych funkcji, ale możliwe, że to też nie jest optymalne):

def comb(a, n):
    aa = [set() for i in range(len(a))]
    for i in range(len(a)):
        aa[i].add(a[i])
    for i in range(n-1):
        z = []
        for elem in a:
            for e in aa:
                u = e.copy()
                u.add(elem)
                if not u in z and len(u)==i+2:
                    z.append(u)
        aa = z.copy()
    return aa

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

@hurgadion dzieki za starania ale mam złe wieści :P
w pierwszym powyższym przykładzie, skrypcik źle zadziała przy chęci wygenerować par dwóch elementów print(powerset([1, 2, 3, 4, 5, 6], 2)) - daje nam 30 wyników a powinno być 45
Drugi przykład natomiast, generuje po wszystkie możliwe połączenia, ale brakuje kolejnego kroku by wygenerowane podzbiory, połączyć ze sobą we wszystkie możliwości by nie było części wspólnej :P

1

Hej, przetestuj teraz, ale w miarę dokładnie, w dalszym ciągu dopuszczam możliwość błędu, ale ostrożnie, obsługi błędów niet... :)

def comb(a, k):
    aa = [set() for i in range(len(a))]
    for i in range(len(a)):
        aa[i].add(a[i])
    for i in range(k-1):
        z = []
        for elem in a:
            for e in aa:
                u = e.copy()
                u.add(elem)
                if not u in z and len(u)==i+2:
                    z.append(u)
        aa = z.copy()
    return aa

def powerset(a, n):
    w = []
    x = comb(a, n)
    for e in x:
        for f in x:
            if len(set(e).union(set(f)))==2*n:
                if not [f, e] in w:
                    w.append([e, f])
    return w

print(powerset([1, 2, 3, 4, 5, 6], 2))
print(len(powerset([1, 2, 3, 4, 5, 6], 2)))
print(powerset([1, 2, 3, 4], 2))

Pozdrawiam... :)

0

Wygląda na to, że działa tak jak powinno :D Dzięki wielkie, mam nadzieje, że uda mi się to jakoś przerobić na php, choć na ten moment za dużo z tego kodu nie kumam :p

2

nie przejmuj się... jak to niektórzy tutaj mówią... ja na... kod latami... moje kody, jak widzisz, proste nie są, ale całkiem możliwe, że da się to zrobić lepiej, nie myślałem nad tym za długo... poza tym czasem nie jest proste przełożyć kod z jednego języka na drugi... może jest jakiś translator w sieci tłumaczący z Pythona na PHP ?? :) druga sugestia: poszukaj algorytmu w sieci i sam zaimplementuj... trzecia sugestia: poszukaj rozwiązań w PHP, wydaje mi się, że wystarczy kod do wypisywania kombinacji zbioru k-elementowego ze zbioru n-elementowego... resztę dostukasz sobie, przy odrobinie wysiłku, sam... Powodzenia... :)

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0