Kombinatoryka

Question

Witam,

Jeśli np. dla zbioru {1, 2, 3} chce uzyskać coś takiego:

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

1 2

1 3

2 1

2 3

3 1

3 2

1

2

3

To to jest jakaś permutacja/wariacja? Jak uzyskać coś takiego?

Comments

Wariacje bez powtórzeń 3 elementów ze zbioru 3 elementowego {1,2,3}:

(1 2 3), (1 3 2), (2 1 3), (2 3 1), (3 1 2), (3 2 1)

Wariacje bez powtórzeń 2 elementów ze zbioru 3 elementowego {1,2,3}:

(1 2), (1 3), (2 1), (2 3), (3 1), (3 2)

Wariacje bez powtórzeń 1 elementu ze zbioru 3 elementowego {1,2,3}:

(1), (2), (3)

Wariacje bez powtórzeń, czyli kolejność istotna... Na liczbę takich wariancji bez powtórzeń jest wzór n!/(n-k)! Gdzie n to ilość elementu zbioru, a k ile elementów z tego zbioru wybieramy.

Answer 1

Są to poszczególne wariacje bez powtórzeń:

- dla całego zbioru (3 liczb) { 1 2 3 ,1 3 2, 2 1 3, 2 3 1, 3 1 2, 3 2 1}

- dla dwóch liczb ze zbioru {1 2, 1 3, 2 1, 2 3 , 3 1 , 3 2}

- dla jednej liczby ze zbioru {1 , 2 , 3}

 

Uzyskać możesz poprzez utworzenie pętli (przykład dla 2 liczb(wyrazów) ze zbioru ):

for(int j = 0 ; j < N ; j++)
   for(int i = 0 ; i < N ; i++)
            if (tab[j] != tab[i])
                  cout<<tab[j]<< " " << tab[i] << endl;

Z im więcej liczb (wyrazów) chcesz wariacje tym więcej pętli ( np. 2 wyrazy z N to dwie pętle, 3 wyrazy z N to trzy pętle itd)

Answer 2

W sensie chcesz wyznaczyć to ile tych elementów będzie? Jeśli tak, to proste:

Najpierw 3 elementy ze zbioru 3 elementowego, potem 2 elementy ze zbioru 3 elementowego, potem 1 element ze zbioru 3 elementowego

Zapisujemy za pomocą dwumianu newtona.

(3 1) + (3 2) + (3 3) = 3 + 6+ 9 = 18.

Jak chcesz uzyskać te wyrazy, a nie ich liczbę, to dla małych zbiorów możesz to zrobić w głowie, dla większych na papierze, a dla naprawdę dużych możesz napisać program, który będzie je wyznaczał. Jak będziesz go pisał, to możesz dodać opcję, aby szukał z powtórzeniami lub bez nich.

Answer 3

Nie, ale spójrz na to w ten sposób: na początku masz tyle miejsc ile jest elementów, robisz dla nich kombinacje bez powtórzeń, następnie twoje miejsce pomniejsza się o 1, jednak twój zbiór się nie zmienia, więc robisz to samo ale dla 2 miejsc i tak aż do 1.

Czylli masz: dla 3 elementowego zbioru: 3*2*1+3*2 + 3