Trouver toutes les partitions d'un ensemble en Java
J'ai la fonction Python suivante pour trouver récursivement toutes les partitions d'un ensemble:
def partitions(set_):
if not set_:
yield []
return
for i in xrange(2**len(set_)/2):
parts = [set(), set()]
for item in set_:
parts[i&1].add(item)
i >>= 1
for b in partitions(parts[1]):
yield [parts[0]]+b
for p in partitions(["a", "b", "c", "d"]):
print(p)
Quelqu'un peut-il m'aider à traduire cela en Java? C'est ce que j'ai jusqu'à présent:
private static List<List<List<String>>> partitions(List<String> inputSet) {
List<List<List<String>>> res = Lists.newArrayList();
if (inputSet.size() == 0) {
List<List<String>> empty = Lists.newArrayList();
res.add(empty);
return res;
}
int limit = (int)(Math.pow(2, inputSet.size())/2);
for (int i = 0; i<limit; i++) {
List<List<String>> parts = Lists.newArrayList();
List<String> part1 = Lists.newArrayList();
List<String> part2 = Lists.newArrayList();
parts.add(part1);
parts.add(part2);
for (String item: inputSet) {
parts.get(i&1).add(item);
i >>= 1;
}
for (List<List<String>> b: partitions(parts.get(1))) {
List<List<String>> set = Lists.newArrayList();
set.add(parts.get(0));
set.addAll(b);
res.add(set);
}
}
return res;
}
J'obtiens une récursivité infinie lors de son exécution avec plus d'un élément.
Un poste similaire à celui-ci (avec Ruby) peut être trouvé ici. L'original du code Python peut être trouvé ici et ici.
1 answers
Vous êtes très proche de la bonne réponse. Vous dites que vous obtenez une récursivité infinie, mais en réalité, le programme s'exécute dans une boucle infinie dans la boucle la plus externe.
La principale différence avec le code Python est que la variable i avance toujours dans la boucle externe dans la version Python, mais dans votre version Java, l'instruction i >>= 1 à l'intérieur de la boucle interne laisse toujours i à zéro. Le moyen facile de résoudre ce problème consiste simplement à utiliser des variables séparées pour l'intérieur et l'extérieur boucle.
, En général, c'est pourquoi c'est une mauvaise idée d'essayer de traduire directement un programme à partir d'une langue à l'autre. Presque tous les programmes ont des idiomes qui ont du sens dans la langue d'origine qui seront bizarres ou dénués de sens dans la langue cible. En particulier, le code Python repose sur la promotion implicite d'entiers de précision arbitraires pour son exactitude. Cela ne fonctionnera pas bien en Java, donc l'implémentation ci-dessous souffre d'un débordement d'entiers si l'ensemble d'entrées est plus grand que 31 éléments. Votre exemple n'est que de 4 éléments, donc pour ce cas spécifique, il produira la bonne réponse.
Voici une version corrigée de Java:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Partition {
private static List<List<List<String>>> partitions(List<String> inputSet) {
List<List<List<String>>> res = new ArrayList<>();
if (inputSet.isEmpty()) {
List<List<String>> empty = new ArrayList<>();
res.add(empty);
return res;
}
// Note that this algorithm only works if inputSet.size() < 31
// since you overflow int space beyond that. This is true even
// if you use Math.pow and cast back to int. The original
// Python code does not have this limitation because Python
// will implicitly promote to a long, which in Python terms is
// an arbitrary precision integer similar to Java's BigInteger.
int limit = 1 << (inputSet.size() - 1);
// Note the separate variable to avoid resetting
// the loop variable on each iteration.
for (int j = 0; j < limit; ++j) {
List<List<String>> parts = new ArrayList<>();
List<String> part1 = new ArrayList<>();
List<String> part2 = new ArrayList<>();
parts.add(part1);
parts.add(part2);
int i = j;
for (String item : inputSet) {
parts.get(i&1).add(item);
i >>= 1;
}
for (List<List<String>> b : partitions(part2)) {
List<List<String>> holder = new ArrayList<>();
holder.add(part1);
holder.addAll(b);
res.add(holder);
}
}
return res;
}
public static void main(String[] args) {
for (List<List<String>> partitions :
partitions(Arrays.asList("a", "b", "c", "d"))) {
System.out.println(partitions);
}
}
}
Voici la sortie de ma version Java:
[[a, b, c, d]]
[[b, c, d], [a]]
[[a, c, d], [b]]
[[c, d], [a, b]]
[[c, d], [b], [a]]
[[a, b, d], [c]]
[[b, d], [a, c]]
[[b, d], [c], [a]]
[[a, d], [b, c]]
[[a, d], [c], [b]]
[[d], [a, b, c]]
[[d], [b, c], [a]]
[[d], [a, c], [b]]
[[d], [c], [a, b]]
[[d], [c], [b], [a]]