Java - Alternativa za vnořené cykly?

Dá se použít například rekurze:

import java.util.ArrayList;
import java.util.List; 
public class CharacterCombinations {

	public static void main(String[] args) {
		char[] charArray = {'a', 'b', 'c', 'd'};
		int length = 4;
		List<String> Combinations = getCombinations(charArray, new ArrayList<String>(), length, "");
		System.out.println(Combinations);
	}

	private static List<String> getCombinations(char[] charArray, List<String> Combinations, int length, String prefix) {
		if(prefix.length()==length){
			Combinations.add(prefix);
		}else{
			for(int i=0; i<charArray.length; i++){
				getCombinations(charArray, Combinations, length, prefix+charArray[i]);
			}
		}
		return Combinations;
		
	}
}

Sorry za opožděnou odpověď. Díky, přesně to jsem chtěl.

Avšak, když tam dám lenght na 14, po chvíli to zhavaruje s java.lang.reflect.InvocationTargetException

Jak, prosím Vás, vyřeším tenhle problém? Při počítání pomocí vnořených cyklů tenhle problém nenastal.

Děkuji

A to ti padá přesně na tomhle kódu, nebo sis to ještě nějak sám upravil?

Ano, jen jsem pochopitelně navýšil počet znaků (počet písmen pořád 4, ale délku jsem nastavil na 14)

Ale jde hlavně o to, že pokud jsem vytvořil několik vnořených cyklů (viz než 4), tak to crashlo kvůli nedostatku paměti, k této chybě nikdy nedošlo.

Toto je její úplné znění

Exception in Application start method
java.lang.reflect.InvocationTargetException
	at java.base/jdk.internal.reflect.DirectMethodHandleAccessor.invoke(DirectMethodHandleAccessor.java:119)
	at java.base/java.lang.reflect.Method.invoke(Method.java:578)
	at javafx.graphics@20.0.1/com.sun.javafx.application.LauncherImpl.launchApplicationWithArgs(LauncherImpl.java:464)
	at javafx.graphics@20.0.1/com.sun.javafx.application.LauncherImpl.launchApplication(LauncherImpl.java:363)
	at java.base/jdk.internal.reflect.DirectMethodHandleAccessor.invoke(DirectMethodHandleAccessor.java:104)
	at java.base/java.lang.reflect.Method.invoke(Method.java:578)
	at java.base/sun.launcher.LauncherHelper$FXHelper.main(LauncherHelper.java:1081)
Caused by: java.lang.RuntimeException: Exception in Application start method
	at javafx.graphics@20.0.1/com.sun.javafx.application.LauncherImpl.launchApplication1(LauncherImpl.java:893)
	at javafx.graphics@20.0.1/com.sun.javafx.application.LauncherImpl.lambda$launchApplication$2(LauncherImpl.java:195)
	at java.base/java.lang.Thread.run(Thread.java:1623)
Caused by: java.lang.OutOfMemoryError: Java heap space
	at java.base/java.lang.StringConcatHelper.newString(StringConcatHelper.java:331)
	at java.base/java.lang.invoke.DirectMethodHandle$Holder.invokeStatic(DirectMethodHandle$Holder)
	at java.base/java.lang.invoke.LambdaForm$MH/0x00000008010a2800.invoke(LambdaForm$MH)
	at java.base/java.lang.invoke.Invokers$Holder.linkToTargetMethod(Invokers$Holder)
	at combination.Variation.getVariation(Variation.java:60)
	at combination.Variation.getVariation(Variation.java:60)
	at combination.Variation.getVariation(Variation.java:60)
	at combination.Variation.getVariation(Variation.java:60)
	at combination.Variation.getVariation(Variation.java:60)
	at combination.Variation.getVariation(Variation.java:60)
	at combination.Variation.getVariation(Variation.java:60)
	at combination.Variation.getVariation(Variation.java:60)
	at combination.Variation.getVariation(Variation.java:60)
	at combination.Variation.getVariation(Variation.java:60)
	at combination.Variation.getVariation(Variation.java:60)
	at combination.Variation.getVariation(Variation.java:60)
	at combination.Variation.getVariation(Variation.java:60)
	at combination.Variation.getVariation(Variation.java:60)
	at combination.Variation.start(Variation.java:47)
	at javafx.graphics@20.0.1/com.sun.javafx.application.LauncherImpl.lambda$launchApplication1$9(LauncherImpl.java:839)
	at javafx.graphics@20.0.1/com.sun.javafx.application.LauncherImpl$$Lambda$102/0x0000000801087528.run(Unknown Source)
	at javafx.graphics@20.0.1/com.sun.javafx.application.PlatformImpl.lambda$runAndWait$12(PlatformImpl.java:483)
	at javafx.graphics@20.0.1/com.sun.javafx.application.PlatformImpl$$Lambda$95/0x0000000801084e88.run(Unknown Source)
	at javafx.graphics@20.0.1/com.sun.javafx.application.PlatformImpl.lambda$runLater$10(PlatformImpl.java:456)
	at javafx.graphics@20.0.1/com.sun.javafx.application.PlatformImpl$$Lambda$97/0x00000008010860b0.run(Unknown Source)
	at java.base/java.security.AccessController.executePrivileged(AccessController.java:778)
	at java.base/java.security.AccessController.doPrivileged(AccessController.java:400)
	at javafx.graphics@20.0.1/com.sun.javafx.application.PlatformImpl.lambda$runLater$11(PlatformImpl.java:455)
	at javafx.graphics@20.0.1/com.sun.javafx.application.PlatformImpl$$Lambda$96/0x0000000801085850.run(Unknown Source)
	at javafx.graphics@20.0.1/com.sun.glass.ui.InvokeLaterDispatcher$Future.run(InvokeLaterDispatcher.java:95)
	at javafx.graphics@20.0.1/com.sun.glass.ui.win.WinApplication._runLoop(Native Method)
	at javafx.graphics@20.0.1/com.sun.glass.ui.win.WinApplication.lambda$runLoop$3(WinApplication.java:185)
Exception running application combination.Variation

a co se ti nezda? Dosla pamet (heap), protoze jsi vytvoril shitload String instanci…

Ano, ale u vnořených cyklů šlo vždy jenom o překročení paměti, žádnou InvocationTargetException to nehlásilo. A právě na to se ptám, jestli to má řešení?

Když si ten chybový callstack přečteš celý, tak zjistiš, že je to taky způsobené nedostatkem paměti.

Ano, ale jak jsem řekl, u vnořených cyklů docházelo POUZE k nedostatku paměti, žádnou InvocationTargetException to nehlásilo. Zajímá mě význam této chyby, který očividně s rekurzí souvisí, protože u vnořených cyklů vždy pouze přetekla paměť.

Problém bude v kódu, který jsi neuvedl. Mám silné tušení, že se ty, dva případy liší víc, než jenom způsobem vytváření variací.

Samotný kód metody jsem nijak neměnil. A jinak je tam pouze jiná inicializace pole a počet předávám přímo pomocí čísla ne proměnné, ale ani jedno z toho ve výsledku nemá žádný vliv.

var charArray = new char[]{'a', 'b', 'c', 'd'};
var variation = getVariation(charArray, new ArrayList<>(), 14, "");
System.out.println(variation.size());

Chtěl bych opětovně otevřít toto téma, na které jsem zanevřel a teď jsem se k tomu opětovně vrátil. Jak už bylo zmíněno, náhrada za vnořené cykly je rekurze, kromě kódu v odpovědi, jsem našel různé způsoby, např. tento

// add the next character to the string, or the string to the list
public void variations(List<String> list, int remaining, String soFar, int... codePoints) {
    if (remaining == 0) {
        list.add(soFar);
    } else {
        for (int i = 0; i < codePoints.length; ++i) {
            variations(list, remaining - 1,
                soFar + Character.toString(codePoints[i]), codePoints);
        }
    }
}

// recursively generate all possible combinations
public List<String> getVariation(int number, int... codePoints) {
    List<String> list = new ArrayList<>();
    variations(list, number, "", codePoints);
    return list;
}

Tento kód jednoduše zavolám příkazem

Zmíněnou chybu java.lang.reflect.InvocationTargetException bych odsunul stranou. Tu zavinila knihovna OpenJavaFX, se kterou je více potíží než užitku (od té doby, co není součástí Java) a po odebrání chyba zmizela.

Avšak, stále tu zůstává problém s nedostatkem paměti. Pokud zavolám kód výše např. tímto příkazem

var list = getVariation(7, "abcdefghijklmnop".codePoints().toArray());

Program poběží cca 3 minuty a pak zhavaruje s chybou Exception in thread "main" java.lang.OutOfMemoryError: Java heap space

Problém přetrvává i potom, co jsem NetBeans navýšil paměť na 5 GB (před tím to zhavarovalo mnohem dříve)

Nevíte, prosím Vás, jak to vyřešit? Samozřejmě je tu ještě problém s nedostatkem kapacity pole, ale to jsem chtěl jednoduše vyřešit použitím více polí.

Nicméně, to bych první musel vyřešit problém s pamětí. Popravdě se mně ani nepodařilo zjistit, jak velké pole vlastně je, když to zhavaruje.

Děkuji za odpověď.

No tak si to spočítáme. Máš tam 16 znaků, děláš variace s opakováním o délce 7. Takže celkem 16^7 = 268435456 variací. Každá z těch variací je 7 znaků dlouhá, znak zabírá v paměti 2 byty. Takže celkem 3758096384 B = 3,5 GB. Ve skutečnosti to bude víc, protože instance stringu nejsou jenom samotné znaky.

Problém je ale i v tom, jak ty variace vytváříš:

soFar + Character.toString(codePoints[i])

Vytvoří nový string, do kterého nakopíruje původní a k tomu ten jeden znak. Najednou máš v paměti ten string prakticky dvakrát, než to uklidí garbage collector. A pokud je vytváříš rychleji, než se stihne uklízet, tak ti dojde paměť.

No, popravdě to jediný kód. Ten, co jsem zmínil, se mně líbil právě v předání těch znaků v jednom řetězci, avšak existuje ještě tento

String[] array = new String[]{"a", "b", "c", "d"};

public static List<String> create(int maxLength, String[] array){
    List<String> strings = new ArrayList<>();
    strings.addAll(create("",0, maxLength, array));
    return strings;
}

private static List<String> create(String current, int currentLength, int maxLength, String[] array){
    List<String> strings = new ArrayList<>();
    if(currentLength < maxLength){
        for(int x=0;x<array.length;x++){
           strings.addAll(create(current + array[x],currentLength + 1, maxLength, array));
        }
    }else{
        strings.add(current);
    }
    return strings;
}

A pak ještě tento

var chars = new char[] {'a', 'b', 'c'};
int variations = 3;
    
var length = chars.length;
var list = new ArrayList<String>();
StringBuilder out = new StringBuilder();

for (int i = 0; i < variations; i++) out.append(chars[0]);

top:
while (true) {
  list.add(out.toString());
  for (int pos = variations - 1; pos >= 0; pos--) {
    char c = out.charAt(pos);
    int cPos = Arrays.binarySearch(chars, c);
    if (cPos < length -1) {
      // We can just increment this one and we're done
      out.setCharAt(pos, chars[cPos + 1]);
      continue top;
    } else {
      // 9-> 10: Every 'lower' digit is reset to first (0).
      out.setCharAt(pos, chars[0]);
    }
  }
  break;
}

Který kód je ale nejoptimálnější, to nevím. To bych musel napsat JUnit test. Nicméně, momentálně to není podstatné, protože vždy to zhavaruje stejnou chybou.

A pokud je vytváříš rychleji, než se stihne uklízet, tak ti dojde paměť.

V tom případě by stačilo použít System.gc();. Otázkou je, kam ho přesně dát a jestli by to pomohlo.

Pak by se jeste mohl podivat, co dela metoda ensureCapacity na ArrayListu...

Určitě ano. Ale tady bych už to viděl jako ten nejmenší problém.

No to je dost velky problem, protoze se ten list musi prekopirovat, ale da se vyresit nastavenim pocatecni kapacity.

Asi bych ty variace neukládal (k čemu je vlastně potřebuješ ???), ale každou hned "použil". Nějak mi uniká, k čemu to může být dobré ... Jinak, nemá smysl řešit něco, co vlastně k ničemu není aneb udělal bych to jinak.

Asi bych ty variace neukládal (k čemu je vlastně potřebuješ ???)

To máte asi pravdu, přímým použitím by paměť nepřetekla. Jenže napsat kód, který první ty variace vytvoří do pole a až potom je využije, je mnohem přehlednější, než když je budu používat hned při vytváření.

Uloz si je do souboru, ne do pameti a pak je cti rovnou ze souboru. Velikost hedne variace znas, tak muzes rovnou precist tu n-tou, ktera te zajima

Uloz si je do souboru, ne do pameti a pak je cti rovnou ze souboru.

To je velmi zajímavá myšlenka, která mě upřímně nenapadla, jenže vůbec netuším, jak ten kód upravit.

Místo přidání do listu do zapíšeš do souboru.
Ale spíš bys měl zodpovědět otázku, proč ty variace chceš mít vygenerované. Mám takové tušení, že je vůbec nepotřebuješ.

    public static void main(String[] args) {
        var chars = "abcdefghijklmnop".toCharArray();
        int variations = 7;

        var length = chars.length;
        var list = new LinkedList<String>();
        StringBuilder out = new StringBuilder();

        for (int i = 0; i < variations; i++) out.append(chars[0]);

        top:
        while (true) {
            list.add(out.toString());
            if (list.size() % 10000 == 0) {
                append(list);
                list.clear();
            }
            for (int pos = variations - 1; pos >= 0; pos--) {
                char c = out.charAt(pos);
                int cPos = Arrays.binarySearch(chars, c);
                if (cPos < length - 1) {
                    // We can just increment this one and we're done
                    out.setCharAt(pos, chars[cPos + 1]);
                    continue top;
                } else {
                    // 9-> 10: Every 'lower' digit is reset to first (0).
                    out.setCharAt(pos, chars[0]);
                }
            }
            break;
        }
    }

    public static void append(List<String> combinations) {
        try {
            Files.write(Paths.get("combinations.txt"), String.join("\n", combinations).getBytes(),
                    StandardOpenOption.APPEND, StandardOpenOption.CREATE);
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

Ukladani do souboru combinations.txt. A nepotrebujes ani zadne gigabajty heapu. Jako mustr jsem pouzil jeden z tvych kodu, co jsi jsem dal. Ten ktery se mi zdal nejlepsi...

Mala chybicka, zapomnel jsem zapsat posledni davku kombinaci. Oprava:

    public static void main(String[] args) {
        var chars = "abcdefghijklmnop".toCharArray();
        int variations = 7;

        var length = chars.length;
        var list = new LinkedList<String>();
        StringBuilder out = new StringBuilder();

        for (int i = 0; i < variations; i++) out.append(chars[0]);

        top:
        while (true) {
            list.add(out.toString());
            if (list.size() % 10000 == 0) {
                append(list);
                list.clear();
            }
            for (int pos = variations - 1; pos >= 0; pos--) {
                char c = out.charAt(pos);
                int cPos = Arrays.binarySearch(chars, c);
                if (cPos < length - 1) {
                    // We can just increment this one and we're done
                    out.setCharAt(pos, chars[cPos + 1]);
                    continue top;
                } else {
                    // 9-> 10: Every 'lower' digit is reset to first (0).
                    out.setCharAt(pos, chars[0]);
                }
            }
            break;
        }
        append(list);
    }

    public static void append(List<String> combinations) {
        try {
            Files.write(Paths.get("combinations.txt"), String.join(System.lineSeparator(), combinations).getBytes(),
                    StandardOpenOption.APPEND, StandardOpenOption.CREATE);
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

Ted uz budou v souboru vsechny kombinace...

Proč ??? Prostě ve vhodnou chvíli zavoláš funkci ... a ta funkce může být "uvnitř" libovolně složitá.

Ale pořád jsi neodpověděl, k čemu je vlastně potřebuješ. Třeba se právě v tom skrývá odpověď, jak to celé dělat mnohem lépe.