Перестановки целых чисел (без дублирования)

Question

Я хочу программу, которая принимает 8-значное число и возвращает все его перестановки.

Например, 12345678 должен вернуть 12345687, 12345768, 12345786 .. 87654321.

Моя идея заключается в том, чтобы сделать это:

Сначала вставьте каждую цифру в качестве элемента в массиве, а затем:

for (int y = 0; y < digits; y++) 
    for (int x = 0; x < digits; x++) 
     for (int u = 0; u < digits; u++) 
      for (int m = 0; m < digits; m++) 
       for (int z = 0; z < digits; z++) 
        for (int b = 0; b < digits; b++) 
         for (int c = 0; c < digits; c++) 
          for (int d = 0; d < digits; d++) 
          { 
           if (!(y == x || y == u || y == m 
            || y == z || y == b || y == c 
            || y == d || x == u || x == m 
            || x == z || x == b || x == c 
            || x == d || u == m || u == z 
            || u == b || u == c || u == d 
            || m == z || m == b || m == c 
            || m == d || z == b || z == c 
            || z == d || b == c || b == d || c == d)) 
           { 

            holding[co] = (a1[y] * 10000000) 
               + (a1[x] * 1000000) 
               + (a1[u] * 100000) 
               + (a1[m] * 10000) 
               + (a1[z] * 1000) 
               + (a1[b] * 100) 
               + (a1[c] * 10) 
               + a1[d]; 

            co++; 
           } 
          } 

И получить все результат в массив. Сортируйте массив и избавьтесь от тех же элементов (например, если ввод 11223344, тогда будут те же элементы).

Но проблема в том, что я действительно хочу напечатать все перестановки чисел от 10000000 до 20000000. Эта идея работает слишком медленно. Кто-нибудь знает, как сделать это быстрее?

Answer 1

Как насчет рекурсивно, как они предлагают здесь?

Generating all permutations of a given string

Логика была несколько улучшена за счет предложений Фама. Я думаю, теперь это O (n) ... Позвольте мне знать, если кто-то видит по-другому.

import java.util.ArrayList; 

    public class Main { 

     static ArrayList<Integer> numbersList = new ArrayList<Integer>(); 
     static ArrayList<String> prefixList = new ArrayList<String>(); 

     public static void main(String[] args) { 
      String number = "83241232"; 

      permutation(number); 

      System.out.printf("Found %d unique permutations!%n", numbersList.size()); 
      for(int i=0; i<numbersList.size(); i++) 
      { 
       System.out.printf("%d%n", numbersList.get(i)); 
      } 
     } 

     public static void permutation(String str) { 
      permutation("", str); 
     } 

     private static void permutation(String prefix, String str) { 
      int n = str.length(); 
      if (n == 0) 
      { 
       if(!prefixList.contains(prefix)) 
       { 
        prefixList.add(prefix); 
        numbersList.add(Integer.parseInt(prefix)); 
       } 
      } 
      else { 
       for (int i = 0; i < n; i++) 
       { 
        permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n)); 
       } 
      } 
     } 
    } 

Answer 2

для одного слишком многих петель это гораздо проще пример, и это только для 10 цифр массива вы можете изменить это, чтобы пройти через все +1000000 или как никогда много вам это нужно, хотя это занимает в то время как.

import java.util.Arrays; 

/** 
* 
* @author David 
*/ 
public class Permutations { 

    /** 
    * @param args the command line arguments 
    */ 
    public static void permutations(int[] chararr,int start, int end) 
    { 
     System.out.println(Arrays.toString(chararr)); 
     if (start<end) 
     { 
      int i,j; 
      for(i=end-2; i>=start; i--) 
      { 
       for(j=i+1; j<end; j++) 
       { 
        Swap(chararr,i,j); 
        permutations(chararr,i+1,end); 
       } 
       Rotate_Left(chararr,i,end); 
      } 
     } 
    } 
    private static void Swap(int[] chararr,int i,int j) 
    { 
     int t; 
     t = chararr[i]; 
     chararr[i] = chararr[j]; 
     chararr[j] = t; 
    } 

    private static void Rotate_Left(int[] chararr,int start,int end) 
    { 
     int tmp = chararr[start]; 
     for (int i=start; i < end-1; i++) 
     { 
      chararr[i] = chararr[i+1]; 
     } 
     chararr[end-1] = tmp; 
    }   

    public static void main(String[] args) { 
     // TODO code application logic here 
     int[] array = new int[10]; 
     for(int x = 0; x < array.length; x++) 
      array[x] = x+1; 
     permutations(array,0,array.length); 

    } 

}