"Forstår det slik at det kan være {A, B} eller {B, A} men ikke begge."
Ja, det stemmer. utrykte meg kanskje litt klossete.
Men nå har jeg faktisk funnet en løsning. Det handlet mest om å vite hva jeg skulle skrive inn i google. Det jeg ønsker hadde faktisk et navn : power set (vet ikke hva det er på norsk)
power set av ett sett S, er settet av alle subsett til S
Det finnes mange algoritmer. Jeg kan jo vise den ene her for de som er interessert. Den var nemlig ganske kul.
Først:
Antallet sett i power settet er lik 2^n, hvor n er antall elementer i det settet vi starter med.
Vi teller da med det tomme settet {}.
Dette betyr at vi kan bruke binærtall for å representere alle settene:
{A, B, C} her er n lik 3. 2^3 = 8
da skriver vi 0 til 7 binært:
000
001
010
011
100
101
110
111
Nå kan vi bruke hver bit her som indikator på hvorvidt A, B og/eller C skal være "slått på" i subsettet.
Eks:
{A, B, C}
000 => {}
001 => {C}
010 => {B}
011 => {B,C}
100 => {A}
101 => {A,C}
110 => {A,B}
111 => {A,B,C}
Her er alle subsettene med!
Vi lager altså en vanlig for-loop som oppdaterer en teller fra 0 til 7 (8 tall).
Og for hver gang vi er i loopen konverterer vi int'en vi bruker som teller til binærformat. Leser hver bit, og avgjør på bakgrunn av disse hvilke av elementen A, B og C som skal være med.
Et java eksempel som skriver subsettene til skjerm:
public static void main(String[] args) {
char[] arr = {'A', 'B', 'C'};
int antallSubSett = (int) Math.pow(2, arr.length);
String binStr; //En streng som representerer et binært tall.
for (int x = 0; x < antallSubSett; x++){
binStr = intToBinary(x, arr.length);
//kaller denne metoden pga strengen som representerer
//binærtallet må være like langt som antall elementer
//i arrayen. Metoden legger til 0'er foran tallet
//for å oppnå dette
//Finnes sikkert andre løsninger i andre språk.
for (int y = 0; y < arr.length; y++){
//sjekker hver "bit" i strengen for å avgjøre hvilke element i
// i arr som skal skrives ut
if (binStr.charAt(y) == '1')
System.out.print(arr[y]);
}
System.out.println();
}
}
// denne returnerer en streng bestående av 1'er og 0'er som representerer et binært tall
// argumentet digits sier hvor lang vi vil at strengen skal være:
// 2 er feks lik 10..setter vi digits til 4 vil metoden returnere "0010", digits = 3 returnerer "010"
private static String intToBinary(int binary, int digits) {
String temp = Integer.toBinaryString(binary);
int foundDigits = temp.length();
String str = temp;
for (int i = foundDigits; i < digits; i++) {
str = "0" + str;
}
return str;
}
Og her er en rekursiv løsning jeg fant. Rekursive løsninger er jo stilige å se på alltid. Men vet ikke om denne er kjappere enn den over. Det er faktisk viktig her, det blir kjapt svært mange looper.
Dobler jo antall looper for hvert ekstra element i settet (arrayen). Tilsvarende blir det jo maaange kall av metoden i rekursjonen også.
public class PowerSet {
void run(String[] sa) {
f(sa, 0, "");
}
void f(String[] a, int idx, String s) {
if (idx >= a.length)
return;
System.out.println(s+a[idx]);
f(a, idx+1, s);
f(a, idx+1, s+a[idx]);
}
public static void main(String[] args) {
String[] sa = {"a", "b", "c", "d"};
new PowerSet().run(sa);
}
}
