fork download
copy 
  1. import java.util.ArrayList;
  2. import java.util.List;
  3. import java.util.Set;
  4. import java.util.TreeSet;
  5. import java.util.stream.Collectors;
  6. import java.util.stream.IntStream;
  7.  
  8. final class Combinacoes {
  9.  
  10.     private static final class Volante {
  11.         private final Set<Integer> numeros;
  12.  
  13.         public Volante(int... valores) {
  14.             this.numeros = IntStream.of(valores).boxed().collect(Collectors.toCollection(TreeSet::new));
  15.         }
  16.  
  17.         public int dissimilaridade(Volante outro) {
  18.             List<Integer> interseccao = new ArrayList<>(numeros);
  19.             interseccao.removeAll(outro.numeros);
  20.             return interseccao.size();
  21.         }
  22.  
  23.         @Override
  24.         public String toString() {
  25.             return numeros.toString();
  26.         }
  27.     }
  28.  
  29.     public static List<Volante> busca(int quantidade, int numeros) {
  30.     	List<Volante> volantes = new ArrayList<>();
  31.         busca(volantes, new int[quantidade], 0, numeros - quantidade, 0);
  32.         return volantes;
  33.     }
  34.  
  35.     private static void busca(List<Volante> volantes, int[] resultado, int inicio, int fim, int profundidade) {
  36.         for (int x = inicio; x <= fim; x++) {
  37.             resultado[profundidade] = x + 1;
  38.             if (profundidade + 1 >= resultado.length) {
  39.                 volantes.add(new Volante(resultado));
  40.             } else {
  41.                 busca(volantes, resultado, x + 1, fim + 1, profundidade + 1);
  42.             }
  43.         }
  44.     }  
  45.  
  46.     private static List<Volante> limitarSimilaridade(List<Volante> volantes, int dissimilaridadeMinima) {
  47.     	List<Volante> dissimilares = new ArrayList<>(volantes.size());
  48.  
  49.         externo:
  50.         for (Volante volante : volantes) {
  51.             for (Volante dejaVu : dissimilares) {
  52.                 if (volante.dissimilaridade(dejaVu) < dissimilaridadeMinima) continue externo;
  53.             }
  54.             dissimilares.add(volante);
  55.         }
  56.         return dissimilares;
  57.     }
  58.  
  59.     public static void main(String[] args) { 
  60.         List<Volante> volantes = busca(6, 10);
  61.         System.out.println(volantes.toString().replace("], ", "]\n"));
  62.         System.out.println("Total de combinacoes: " + volantes.size());
  63.  
  64.         List<Volante> filtrados = limitarSimilaridade(volantes, 2);
  65.         System.out.println("Tamanho final: " + filtrados.size());
  66.         System.out.println("Resultado final");
  67.         System.out.println(filtrados.toString().replace("], ", "]\n"));
  68.     }  
  69. }
Success #stdin #stdout 0.11s 711680KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 7]
[1, 2, 3, 4, 5, 8]
[1, 2, 3, 4, 5, 9]
[1, 2, 3, 4, 5, 10]
[1, 2, 3, 4, 6, 7]
[1, 2, 3, 4, 6, 8]
[1, 2, 3, 4, 6, 9]
[1, 2, 3, 4, 6, 10]
[1, 2, 3, 4, 7, 8]
[1, 2, 3, 4, 7, 9]
[1, 2, 3, 4, 7, 10]
[1, 2, 3, 4, 8, 9]
[1, 2, 3, 4, 8, 10]
[1, 2, 3, 4, 9, 10]
[1, 2, 3, 5, 6, 7]
[1, 2, 3, 5, 6, 8]
[1, 2, 3, 5, 6, 9]
[1, 2, 3, 5, 6, 10]
[1, 2, 3, 5, 7, 8]
[1, 2, 3, 5, 7, 9]
[1, 2, 3, 5, 7, 10]
[1, 2, 3, 5, 8, 9]
[1, 2, 3, 5, 8, 10]
[1, 2, 3, 5, 9, 10]
[1, 2, 3, 6, 7, 8]
[1, 2, 3, 6, 7, 9]
[1, 2, 3, 6, 7, 10]
[1, 2, 3, 6, 8, 9]
[1, 2, 3, 6, 8, 10]
[1, 2, 3, 6, 9, 10]
[1, 2, 3, 7, 8, 9]
[1, 2, 3, 7, 8, 10]
[1, 2, 3, 7, 9, 10]
[1, 2, 3, 8, 9, 10]
[1, 2, 4, 5, 6, 7]
[1, 2, 4, 5, 6, 8]
[1, 2, 4, 5, 6, 9]
[1, 2, 4, 5, 6, 10]
[1, 2, 4, 5, 7, 8]
[1, 2, 4, 5, 7, 9]
[1, 2, 4, 5, 7, 10]
[1, 2, 4, 5, 8, 9]
[1, 2, 4, 5, 8, 10]
[1, 2, 4, 5, 9, 10]
[1, 2, 4, 6, 7, 8]
[1, 2, 4, 6, 7, 9]
[1, 2, 4, 6, 7, 10]
[1, 2, 4, 6, 8, 9]
[1, 2, 4, 6, 8, 10]
[1, 2, 4, 6, 9, 10]
[1, 2, 4, 7, 8, 9]
[1, 2, 4, 7, 8, 10]
[1, 2, 4, 7, 9, 10]
[1, 2, 4, 8, 9, 10]
[1, 2, 5, 6, 7, 8]
[1, 2, 5, 6, 7, 9]
[1, 2, 5, 6, 7, 10]
[1, 2, 5, 6, 8, 9]
[1, 2, 5, 6, 8, 10]
[1, 2, 5, 6, 9, 10]
[1, 2, 5, 7, 8, 9]
[1, 2, 5, 7, 8, 10]
[1, 2, 5, 7, 9, 10]
[1, 2, 5, 8, 9, 10]
[1, 2, 6, 7, 8, 9]
[1, 2, 6, 7, 8, 10]
[1, 2, 6, 7, 9, 10]
[1, 2, 6, 8, 9, 10]
[1, 2, 7, 8, 9, 10]
[1, 3, 4, 5, 6, 7]
[1, 3, 4, 5, 6, 8]
[1, 3, 4, 5, 6, 9]
[1, 3, 4, 5, 6, 10]
[1, 3, 4, 5, 7, 8]
[1, 3, 4, 5, 7, 9]
[1, 3, 4, 5, 7, 10]
[1, 3, 4, 5, 8, 9]
[1, 3, 4, 5, 8, 10]
[1, 3, 4, 5, 9, 10]
[1, 3, 4, 6, 7, 8]
[1, 3, 4, 6, 7, 9]
[1, 3, 4, 6, 7, 10]
[1, 3, 4, 6, 8, 9]
[1, 3, 4, 6, 8, 10]
[1, 3, 4, 6, 9, 10]
[1, 3, 4, 7, 8, 9]
[1, 3, 4, 7, 8, 10]
[1, 3, 4, 7, 9, 10]
[1, 3, 4, 8, 9, 10]
[1, 3, 5, 6, 7, 8]
[1, 3, 5, 6, 7, 9]
[1, 3, 5, 6, 7, 10]
[1, 3, 5, 6, 8, 9]
[1, 3, 5, 6, 8, 10]
[1, 3, 5, 6, 9, 10]
[1, 3, 5, 7, 8, 9]
[1, 3, 5, 7, 8, 10]
[1, 3, 5, 7, 9, 10]
[1, 3, 5, 8, 9, 10]
[1, 3, 6, 7, 8, 9]
[1, 3, 6, 7, 8, 10]
[1, 3, 6, 7, 9, 10]
[1, 3, 6, 8, 9, 10]
[1, 3, 7, 8, 9, 10]
[1, 4, 5, 6, 7, 8]
[1, 4, 5, 6, 7, 9]
[1, 4, 5, 6, 7, 10]
[1, 4, 5, 6, 8, 9]
[1, 4, 5, 6, 8, 10]
[1, 4, 5, 6, 9, 10]
[1, 4, 5, 7, 8, 9]
[1, 4, 5, 7, 8, 10]
[1, 4, 5, 7, 9, 10]
[1, 4, 5, 8, 9, 10]
[1, 4, 6, 7, 8, 9]
[1, 4, 6, 7, 8, 10]
[1, 4, 6, 7, 9, 10]
[1, 4, 6, 8, 9, 10]
[1, 4, 7, 8, 9, 10]
[1, 5, 6, 7, 8, 9]
[1, 5, 6, 7, 8, 10]
[1, 5, 6, 7, 9, 10]
[1, 5, 6, 8, 9, 10]
[1, 5, 7, 8, 9, 10]
[1, 6, 7, 8, 9, 10]
[2, 3, 4, 5, 6, 7]
[2, 3, 4, 5, 6, 8]
[2, 3, 4, 5, 6, 9]
[2, 3, 4, 5, 6, 10]
[2, 3, 4, 5, 7, 8]
[2, 3, 4, 5, 7, 9]
[2, 3, 4, 5, 7, 10]
[2, 3, 4, 5, 8, 9]
[2, 3, 4, 5, 8, 10]
[2, 3, 4, 5, 9, 10]
[2, 3, 4, 6, 7, 8]
[2, 3, 4, 6, 7, 9]
[2, 3, 4, 6, 7, 10]
[2, 3, 4, 6, 8, 9]
[2, 3, 4, 6, 8, 10]
[2, 3, 4, 6, 9, 10]
[2, 3, 4, 7, 8, 9]
[2, 3, 4, 7, 8, 10]
[2, 3, 4, 7, 9, 10]
[2, 3, 4, 8, 9, 10]
[2, 3, 5, 6, 7, 8]
[2, 3, 5, 6, 7, 9]
[2, 3, 5, 6, 7, 10]
[2, 3, 5, 6, 8, 9]
[2, 3, 5, 6, 8, 10]
[2, 3, 5, 6, 9, 10]
[2, 3, 5, 7, 8, 9]
[2, 3, 5, 7, 8, 10]
[2, 3, 5, 7, 9, 10]
[2, 3, 5, 8, 9, 10]
[2, 3, 6, 7, 8, 9]
[2, 3, 6, 7, 8, 10]
[2, 3, 6, 7, 9, 10]
[2, 3, 6, 8, 9, 10]
[2, 3, 7, 8, 9, 10]
[2, 4, 5, 6, 7, 8]
[2, 4, 5, 6, 7, 9]
[2, 4, 5, 6, 7, 10]
[2, 4, 5, 6, 8, 9]
[2, 4, 5, 6, 8, 10]
[2, 4, 5, 6, 9, 10]
[2, 4, 5, 7, 8, 9]
[2, 4, 5, 7, 8, 10]
[2, 4, 5, 7, 9, 10]
[2, 4, 5, 8, 9, 10]
[2, 4, 6, 7, 8, 9]
[2, 4, 6, 7, 8, 10]
[2, 4, 6, 7, 9, 10]
[2, 4, 6, 8, 9, 10]
[2, 4, 7, 8, 9, 10]
[2, 5, 6, 7, 8, 9]
[2, 5, 6, 7, 8, 10]
[2, 5, 6, 7, 9, 10]
[2, 5, 6, 8, 9, 10]
[2, 5, 7, 8, 9, 10]
[2, 6, 7, 8, 9, 10]
[3, 4, 5, 6, 7, 8]
[3, 4, 5, 6, 7, 9]
[3, 4, 5, 6, 7, 10]
[3, 4, 5, 6, 8, 9]
[3, 4, 5, 6, 8, 10]
[3, 4, 5, 6, 9, 10]
[3, 4, 5, 7, 8, 9]
[3, 4, 5, 7, 8, 10]
[3, 4, 5, 7, 9, 10]
[3, 4, 5, 8, 9, 10]
[3, 4, 6, 7, 8, 9]
[3, 4, 6, 7, 8, 10]
[3, 4, 6, 7, 9, 10]
[3, 4, 6, 8, 9, 10]
[3, 4, 7, 8, 9, 10]
[3, 5, 6, 7, 8, 9]
[3, 5, 6, 7, 8, 10]
[3, 5, 6, 7, 9, 10]
[3, 5, 6, 8, 9, 10]
[3, 5, 7, 8, 9, 10]
[3, 6, 7, 8, 9, 10]
[4, 5, 6, 7, 8, 9]
[4, 5, 6, 7, 8, 10]
[4, 5, 6, 7, 9, 10]
[4, 5, 6, 8, 9, 10]
[4, 5, 7, 8, 9, 10]
[4, 6, 7, 8, 9, 10]
[5, 6, 7, 8, 9, 10]]
Total de combinacoes: 210
Tamanho final: 18
Resultado final
[[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 7, 8]
[1, 2, 3, 4, 9, 10]
[1, 2, 3, 5, 7, 9]
[1, 2, 3, 5, 8, 10]
[1, 2, 3, 6, 7, 10]
[1, 2, 3, 6, 8, 9]
[1, 2, 4, 5, 7, 10]
[1, 2, 4, 5, 8, 9]
[1, 2, 4, 6, 7, 9]
[1, 2, 4, 6, 8, 10]
[1, 2, 5, 6, 7, 8]
[1, 2, 5, 6, 9, 10]
[1, 2, 7, 8, 9, 10]
[3, 4, 5, 6, 7, 8]
[3, 4, 5, 6, 9, 10]
[3, 4, 7, 8, 9, 10]
[5, 6, 7, 8, 9, 10]]
https://ideone.com/8H0vC3
language:
Java (HotSpot 12)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!