| Kombinaatiot.java |
1 package demo.d1;
2
3 import java.util.ArrayList;
4 // import java.util.Arrays;
5 import java.util.List;
6
7 /**
8 * Etsitään mikä on todennäköisyys voittaa seuraavassa pelissä:
9 * On 3:n värisiä palloja. Niistä poimitaan 4 kappaletta.
10 * Sitten poimitaan vielä 2 kappaletta. Pelissä voittaa
11 * mikäli nämä 2 palloa löytyvät 4 pallon joukosta.
12 * Eli jos molemmat pallot ovat punaisia, pitää neljän pallon
13 * joukossa olla myös olla 2 punaista (yksi ei riitä).
14 *
15 * Ratkaisu tehdään etsimällä ensin kaikki kuuden pallon
16 * mahdolliset joukot. Näistä lasketaan monellako
17 * kaksi ensimmäistä kuuluu loppuun joukkoon.
18 * @author vesal
19 * @version 2.1.2012
20 */
21 public class Kombinaatiot {
22
23 /**
24 * Lasketaan ja tulostetaan kaikki 6 pallon kombinaatiot
25 * @param args ei käytössä
26 */
27 public static void main(String[] args) {
28 int vareja = 3;
29 int ekakoko = 4;
30 int tokakoko = 2;
31
32 List<Integer> varienJoukko = new ArrayList<Integer>();
33 for (int i=0; i<vareja; i++) varienJoukko.add(i);
34 List<List<Integer>> kaikkiJoukot = etsiKombinaatiot(ekakoko+tokakoko,varienJoukko);
35 for (List<Integer> kombi : kaikkiJoukot)
36 System.out.println(kombi);
37
38 /*
39 List<String> varienJoukko = Arrays.asList("pun","vih","sin");
40 List<List<String>> kaikkiJoukot = etsiKombinaatiot(ekakoko+tokakoko,varienJoukko);
41 for (List<String> kombi : kaikkiJoukot)
42 System.out.println(kombi);
43 */
44 }
45
46
47 /**
48 * Etsii kaikki n kokoiset joukot, jossa on alkioita joukosta valinnat
49 * @param n kuinka suuri ajoukkoja etsitään
50 * @param valinnat jokko alkioita joita voidaan valita
51 * @return kaikkien kombinaatioiden joukko
52 * @example
53 * <pre name="test">
54 * #import java.util.List;
55 * List<String> valinnat = Arrays.asList("a","b","c");
56 * List<List<String>> kombit = etsiKombinaatiot(2,valinnat);
57 * int i=0;
58 * kombit.get(i++).toString() === "[a, a]";
59 * kombit.get(i++).toString() === "[a, b]";
60 * kombit.get(i++).toString() === "[a, c]";
61 * kombit.get(i++).toString() === "[b, a]";
62 * kombit.get(i++).toString() === "[b, b]";
63 * kombit.get(i++).toString() === "[b, c]";
64 * kombit.get(i++).toString() === "[c, a]";
65 * kombit.size() === 9;
66 * </pre>
67 */
68 public static<T> List<List<T>> etsiKombinaatiot(int n, List<T> valinnat) {
69 List<List<T>> tulos = new ArrayList<List<T>>();
70 int[] indeksit = new int[n]; // alustettu 0:illa
71 int m = valinnat.size();
72 while ( true ) {
73 List<T> rivi = new ArrayList<T>();
74 for (int i:indeksit)
75 rivi.add(valinnat.get(i));
76 tulos.add(rivi);
77 if ( !kasvata(indeksit,m) ) break;
78 }
79 return tulos;
80 }
81
82
83 /**
84 * Kasvattaa indeksitaulukon "arvoa" yhdellä.
85 * Kukin indeksi voi olla luku 0-(m-1).
86 * @param indeksit taulukko, jota "kasvatetaan"
87 * @param m mikä on rajana yhdelle luvulle
88 * @return true jos pystyi kasvattamaan
89 * @example
90 * <pre name="test">
91 * #import java.util.Arrays;
92 * int[] ind = new int[2];
93 * Arrays.toString(ind) === "[0, 0]"; kasvata(ind,3)=== true;
94 * Arrays.toString(ind) === "[0, 1]"; kasvata(ind,3)=== true;
95 * Arrays.toString(ind) === "[0, 2]"; kasvata(ind,3)=== true;
96 * Arrays.toString(ind) === "[1, 0]"; kasvata(ind,3)=== true;
97 * Arrays.toString(ind) === "[1, 1]"; kasvata(ind,3)=== true;
98 * Arrays.toString(ind) === "[1, 2]"; kasvata(ind,3)=== true;
99 * Arrays.toString(ind) === "[2, 0]"; kasvata(ind,3)=== true;
100 * Arrays.toString(ind) === "[2, 1]"; kasvata(ind,3)=== true;
101 * Arrays.toString(ind) === "[2, 2]"; kasvata(ind,3)=== false;
102 * Arrays.toString(ind) === "[0, 0]";
103 * </pre>
104 */
105 public static boolean kasvata(int[] indeksit, int m) {
106 int n = indeksit.length;
107 for (int i=n-1; i>=0; i--) {
108 indeksit[i]++;
109 if ( indeksit[i] < m ) return true;
110 indeksit[i] = 0;
111 }
112 return indeksit[0] != 0;
113 }
114
115 }
116