Keskustelu: Ohjelmointikysymykset: Java: Kombinaatio

Miten tätä voi parantaa? Sen kyllä tiedän, että taulukkoa tähän ei tarvita.

public class Kombinaatio
{
    public static void main(String[] args) {
        int koko = 7;
        int luvut = 5;
        int luku[] = new int[koko];
        //Laitetaan alkutilanne
        for (int x = 0; x < koko; x++){
            luku[x] = 1+x;
        }
        int maara = 0;
        //Muodostetaan kombinaatioita
        while (luku[0] <= luvut){
          maara++;
          //Kombinaatiossa seuraava luku on aina edellistä suurempi.
          //Lukujen järjestykselllä ei ole merkitystä toisin kuin permutaatiossa.
          for (int x = koko-1; x > 0; x--){
              if (luku[x] > luvut+x){
                  luku[x-1]++;
                  for (int y = x; y < koko; y++){
                  //Seuraavag luvut ovat edellistä suurempia.
                      luku[y] = luku[y-1]+1;
                  }
              }
          }
          if (luku[0] <= luvut){
           System.out.print(maara + ":");
           for (int x = 0; x < koko; x++){
                System.out.print(luku[x] + " ");
           }
           System.out.println("");
          }
          luku[koko-1]++;
        }
    }
}

Ainakin siten että korjataan ettei ole C++ vaan Javaa.

Kai nyt terve järki sanoo, että kombinaatiota on pakko säilyttää jossain kokonaisena, jotta sen pystyy tulostamaan tuolla tavalla. Eli taulukosta ei pääse eroon.

Olisi järkevää valita muuttujat sillä tavalla, että niistä näkisi, mitä lukuja koodi tuottaa. Esimerkiksi tuossa on kohtalainen yllätys, että kombinaatiot muodostuvat lukuvälistä 1–11, kun koodissa esiintyvät vain luvut 5 ja 7.

Jos tarvitaan kombinaatioita, lähtötietoina on yleensä joukon koko ja kombinaation koko. Voisit siis yrittää tehdä koodin, joka tuottaa K jäsenen kombinaatiot lukujoukosta 0 – N-1 (tai 1 – N). Koodi alkaa näin (eikä sisällä muita maagisia lukuja):

final int N = 11;
final int K = 5;

// Tulos:
// 0 1 2 3 4
// 0 1 2 3 5
// ...
// 6 7 8 9 10

Tämän tavan hyöty on siinä, että tuotettuja lukuja voi helposti soveltaa myös muiden tietojen kanssa, kun tiedot saa haettua taulukosta:

String henkilöt[] = {"Matti", "Maija", "Petteri"};
final int N = henkilöt.length;
final int K = 2;

// Tulos:
// 0 1 => henkilöt[0], henkilöt[1] => "Matti", "Maija"
// 0 2 => henkilöt[0], henkilöt[2] => "Matti", "Petteri"
// 1 2 => henkilöt[1], henkilöt[2] => "Maija", "Petteri"

Kombinaatioita voi muodostaa myös rekursiivisella funktiolla, mutta perusidea ei olennaisesti eroa nykyisestä. Rekursiosta voit lukea esimerkiksi rekursio-oppaasta; kombinaatioiden muodostaminen on rekursion kannalta lähes sama ongelma kuin yhdistelmien muodostaminen. Vaikka puun tulostus onnistuu ilman taulukkoa, käytännössä taulukko on edelleen tarpeen, jotta kombinaatiota pystyy koodissa myös jotenkin järkevästi hyödyntämään.

Usein silmukkaratkaisu on toteutettu rekursiivisen ratkaisun idealla, eli harjoituksena voisit tehdä rekursiivisen ratkaisun ja sitten sen ratkaisun, jossa rekursiologiikka tapahtuukin vain silmukassa.