Keskustelu: Yleinen keskustelu: Kaikkien kombinaatioiden läpikäynti

Ongelma yhden brute force -laskun kanssa. Eli mulla on kahdeksan alkioita, olkoon vaikka

[1][2][3][4][5][6][7][8]

pitäisi saada käytyä läpi kaikki mahdolliset järjestykset, johon nuo voivat järjestyä (kertoma). Minkähänlaisella algoritmilla tämä onnistuu?

Jonkinlainen rekursiivinen funktio on hyvä ratkaisu.

Tässä on pari hyödyllistä linkkiä:
https://www.ohjelmointiputka.net/oppaat/opas.php?tunnus=rekursio#yhdistelmienmuodostaminen
https://www.ohjelmointiputka.net/koodivinkit/24950-c-järjestykset-ja-osajoukot

Esim. rekursiolla.. ;) Se on ehkä ainut tapa, jos alkioita on n verran. En sitten tiedä, että onko joissakin "eksoottisemmissa" (kuin java & php) hienoja valmiita funkkareita tähänkin.

Ah, unohdin Antin matematiikka-oppaat kokonaan! Tuosta pääsee eteenpäin, kiitokset kummallekkin!

On siihen toinenkin (käsittääkseni jollain tavalla tehokkaampi) algoritmi, mutta valitettavasti en aivan osaa selittää sitä. Sitä kuitenkin käyttää ainakin C++:n STL:n funktio.

int luvut[8] = {1,2,3,4,5,6,7,8}; // pienuusjärjestys
do {
    // Mitä sitten teetkin...
} while (next_permutation(&luvut[0], &luvut[8]));

Ainakin pienen testin perusteella omatekoinen rekursiivinen funktio ja STL:n next_permutation ovat melko tasavahvoja. Aidosti tehokkaamman algoritmin laatiminen on aika toivotonta, kun ohjelman pitää kuitenkin jossain vaiheessa tutkia jokainen mahdollinen järjestys. Tuossa toisessa tavassa on kuitenkin se hyvä puoli, että seuraava järjestys lasketaan suoraan edellisestä, eli kaikkia järjestyksiä ei tarvitse muodostaa samalla kertaa.

STL:n algoritmi on kätevä, koska sillä ei tarvitse laskea useita permutaatiota kerrallaan. Kuitenkin jos kaikki permutaatiot käydään läpi, se häviää yhdessä puolessa Antin ohjelmalle. Antin ohjelma nimittäin muistaa permutaatioiden välillä, mitä aluetta pitää tutkia. STL:n funktio ei voisikaan sellaista tietoa kantaa sisällään, koska sen pitää olla yleiskäyttöinen.

Tämän takia Antin ohjelma voisi jopa sopivassa vertailussa voittaa STL:n algoritmin nopeudessa kaikkia permutaatioita käsitellessä. Epäilen kyllä, että sen saisi aikaan vain, jos Antin ohjelmaa optimoisi kaikenlaisilla rumilla ja kauheilla tavoilla. (Sitten voisi kysyä, miksei STL:n käyttöä myös saa optimoida.)

Joka tapauksessa n!:lle ei tässä voi mitään, joten optimointi on harvoin mielekästä.

STL näyttää käyttävän Dijkstran permutaatioalgoritmia (ainakin tässä yhdessä versiossa, mitä selailin). Se on hyvin yksinkertainen, mutta vaikea ymmärtää suoraan lukemalla. Netistä löytyy materiaalia ilmiselvillä hakusanoilla.

Heapin (Heap lienee erisnimi) rekursiivinen algoritmi on lyhyt ja suhteellisen nopea. Huvin vuoksi esitän sen, sekä pienen ajettavan esimerkkiohjelman. Kieli on C++.

Permutaatiofunktion voisi toteuttaa niin, että se ottaisi funktio-objektin, jota kutsuttaisiin jokaisella permutaatiolla. Sen jälkeen sitä olisi kätevämpi käyttää eri tarkoituksiin. STL:n next_permutation-funktion tyyliseen käyttöön se ei suoraan sovellu, koska se ei edes tuota permutaatiota leksikograafisessa järjestyksessä. Varsinainen ongelma on rekursion sisällään pitämä tila, jonka takia iteratiivisen vastineen koodaaminen on tuskallista.

Algoritmin korrektisuutta en todista tällä kertaa. Ohjelmaa on testattu Unix-työkalujen sort ja uniq avulla, jotta näin, ettei duplikaattipermutaatioita synny, mikä olisi tietenkin karkea virhe. Tulostusrivien lukumäärät olivat odotettuja.

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

const int PERM_MAX = 5; // 6+:n permutaatiojoukot ovat sikaisoja
typedef vector<int> Taulu;

// parempaa tyyliä olisi käyttää iteraattoria
void printPerm (Taulu& p) {
  for (int i=0; i<p.size(); ++i) cout << p[i];
  cout << endl;
}

// testaa, onko luku pariton
inline bool odd (int n) { return n&1; }

// Heapin rekursiivinen permutaatioalgoritmi
// luottaa sokeasti, että n >= 1 joka kutsulla ja taulu oikeaa kokoa
void Hperm (Taulu& p, int n) {
  if (n == 1) printPerm(p);
  else for (int i=0; i<n; ++i) {
         Hperm(p, n-1);
         swap(p[i*odd(n)], p[n-1]);
  }
}

// Jos et pidä Iversonin konvention käytöstä, arvostat varmaankin tätä
// tapaa enemmän. Tämä korvaa swap-lausekkeen yllä.
/* if (odd(n)) swap(p[i], p[n-1]);
   else swap(p[0], p[n-1]);
*/

int main () {
  Taulu kp;
  for (int i=1; i<=PERM_MAX; ++i) {
    cout << i << ":n alkion permutaatiot" << endl;
    kp.push_back(i);
    Hperm(kp, i);
    // kp jää hassuun järjestykseen, järjestettävä
    sort(kp.begin(), kp.end());
  }
}

P.S. Juu, eri int-tyyppien kanssa voisi olla tarkempi.