많은 수의 순열을 데이터베이스에 저장하기

Question

큰 수의 모든 순열을 계산하고 얻어야합니다. 13 개의 숫자가 들어있는 배열과 같습니다. 하지만 인터넷에서 발견 한 코드는 10 개의 값으로 작동했지만 13 개의 숫자로는 예외가 발생하여 작동하지 않습니다. 메모리가 총 순열을 보여주기에 충분하지 않다고합니다. 순열을 인쇄 할 필요가 없습니다. 나를 데이터베이스에 저장하는 것은 완벽 할 것이다. 데이터베이스에 직접 저장하면 계산을 수행 할 수 없습니다. 나는 인터넷에서 이것에 대한 적절한 대답을 찾을 수 없었다.

이것은 순열을 계산하는 데 사용 된 코드입니다.

공용 클래스 PermutationCalc는 {

/** 
    * @param args the command line arguments 
    */ 


    static <E> String arrayToString(E[] arr) { 
     final StringBuffer str = new StringBuffer(); 
     for (E e : arr){ 
      str.append(e.toString()); 
     } 
     return str.toString(); 
    } 

    static <E> ArrayList<E[]> permutations(E[] arr) { 



     final ArrayList<E[]> resultList = new ArrayList<E[]>(); 
     final int l = arr.length; 
     if (l == 0) return resultList; 
     if (l == 1) 
     { 
      resultList.add(arr); 
      return resultList; 
     } 

     E[] subClone = Arrays.copyOf(arr, l - 1); 
     System.arraycopy(arr, 1, subClone, 0, l - 1); 

     for (int i = 0; i < l; ++i){ 
      E e = arr[i]; 
      if (i > 0) subClone[i-1] = arr[0]; 
      final ArrayList<E[]> subPermutations = permutations(subClone); 
      for (E[] sc : subPermutations) 
      { 
       E[] clone = Arrays.copyOf(arr, l); 
       clone[0] = e; 
       System.arraycopy(sc, 0, clone, 1, l - 1); 
       resultList.add(clone); 
      } 
      if (i > 0) subClone[i-1] = e; 
     } 
     return resultList; 
    } 

    static ArrayList<String> permutations(String arr) { 
     final Character[] c = new Character[arr.length()]; 
     for (int i = 0; i < arr.length(); ++i) 
      c[i] = arr.charAt(i); 

     final ArrayList<Character[]> perms = permutations(c); 
     final ArrayList<String> resultList = new ArrayList<String>(perms.size()); 

     for (Character[] p : perms) 
     { 
      resultList.add(arrayToString(p)); 
     } 
     return resultList; 
    } 

    public static void main(String[] args) { 
     //ArrayList<String> str_perms = permutations("abc"); 
     //for (String p : str_perms) System.out.println(p); 

     ArrayList<Integer[]> int_perms = permutations(new Integer[]{ 1, 2, 3,4,5,6,7,8,9,10}); 
     System.gc(); 
     for (Integer[] p : int_perms) System.out.println(arrayToString(p)); 


    } 
    } 

누군가 날 나는 데이터베이스에 저장하고 계산하는 경우를 해결할 수있을 것입니다 여부를 알려 주시기 바랍니다 수 있습니다.

추신 : 13 개를 찾는 데 사용할 수있는 또 다른 효율적인 코드가 있습니까? 순열 값의 그것은이 코드에 보인다

Answer 1

먼저 모든 순열을 얻을하고 데이터베이스에 저장하려고

OutOfMemoryError가 예외 인해 배열 목록에 전체 결과를 저장하는 메모리의 부족으로 발생 시킬수

그래서 전체 결과를 기다리지 않고 파트별로 결과를 데이터베이스 파트에 저장하려고 시도하십시오. 한 번에 100 개의 순열을 고려해 봅시다. 이 변화를 시도 static <E> ArrayList<E[]> permutations(E[] arr) 방법에

, 이것에

for (E[] sc : subPermutations) 
     { 
      E[] clone = Arrays.copyOf(arr, l); 
      clone[0] = e; 
      System.arraycopy(sc, 0, clone, 1, l - 1); 
      resultList.add(clone); 
      if(resultList.size() == 100) { 
       //your code to store current result in the database here. 
       resultList.clear(); //clear the ArrayList. 
      } 
     } 
    if(!resultList.isEmpty()) { 
     //your code to store current result in the database here. 
     resultList.clear(); //clear the ArrayList. 
    } 

또는 이와 유사한 것.

Answer 2

실제로 모든 순열을 저장하는 것은 어리석은 일입니다. 데이터를 한 번 저장하고 데이터의 순열이 필요한 모든 것에 대해 순열 번호 을 저장하십시오. 힌트 : 13 개 항목에 13 개가 있습니다! 순열. 배열 항목이 각각 1 바이트 인 경우에도 6 기가 바이트 이상이 필요합니다 ( ).

Answer 3

재귀 함수를자를 기본 사례가 없으므로 OutOfMemoryError exception이 표시됩니다. 당신이 오류를 얻을 때까지 그냥 스스로를 호출합니다. 이 약 base case

단어 순열이다

private static void permutation(String prefix, String str) { 
    int n = str.length(); 
    if (n == 0) System.out.println(prefix);//or add to arraylist 
    else { 
     for (int i = 0; i < n; i++) 
      permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n)); 
    } 
} 

경우 번호

//remember that permutation can have a repeating value or not. size is the size of the number or simply the number itself numberDraw is how many times you need to draw numbers from the pool 

private static void computePermutation(boolean isRepeting, int size, 
      int numberDraw) { 

     int result = 1; 
     int currentsize = size; 
     for (int i = 0; i < numberDraw; i++) { 
      System.out.println(currentsize); 
      result *= currentsize; 
      if (!isRepeting) { 
       currentsize -= 1; 
      } 
     } 
     System.out.println("premute number: " + result); 
    } 

심판 : recursionpermutation

Answer 4

그냥 몇 가지 간단한 의견을 추가하려면 다음이 그 문제 중 하나처럼 보인다 그 영리함을 요구하는 - 내가 의미하는 것은 물론 N 자리 숫자에 해당하는 N입니다! 다른 순열은, 그러나 우리가 모든 N 자리가 유일하다고 가정한다면! 숫자를 고려하십시오 : 11111 - 단지 1 개의 순열이 있습니다! 11112의 경우 단지 5 개의 순열이 있거나 5가 1을 선택합니다 (5 개의 위치가 있다고 생각하면 두 개의 입력 중 하나를 선택합니다. 가능한 모든 순열을 맹목적으로 계산하는 것보다 먼저 고유 번호를 고려해야합니다. 순열이 존재합니다.

이것은 학교 과제를 때우는 데, 나는 더 이상 말하지 않을 것입니다.

Answer 5

다음은 특정 길이의 모든 순열을 사전 식 순서로 얻는 일반적인 해결책입니다. 이 데이터를 데이터베이스로 펌핑해야하는지 여부에 대한 질문은 다른 곳에서 응답해야합니다.

/** 
* Generates the permutations in lexicographic order. 
*/ 
public class LexicographicPermutationsIterator extends PermutationsIterator implements Iterator<List<Integer>> { 

    public LexicographicPermutationsIterator(int length) { 
     super(length); 
    } 

    @Override 
    protected boolean nextPerm() { 
     boolean got = false; 
     // Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation. 
     int k = -1; 
     for (int i = 0; i < length - 1; i++) { 
      if (indexes.get(i) < indexes.get(i + 1)) { 
       k = i; 
      } 
     } 
     if (k >= 0) { 
      int ak = indexes.get(k); 
      // Find the largest index l such that a[k] < a[l]. 
      int l = k + 1; 
      for (int i = 0; i < length; i++) { 
       if (ak < indexes.get(i)) { 
        l = i; 
       } 
      } 
      // Swap the value of a[k] with that of a[l]. 
      Collections.swap(indexes, k, l); 
      // Reverse the sequence from a[k + 1] up to and including the final element a[n]. 
      Collections.reverse(indexes.subList(k + 1, indexes.size())); 
      // We got one. 
      got = true; 
     } 
     return got; 
    } 

} 

/** 
* Iterates over permutations. 
* 
* Actually - it manages a list of Integers that are used as indexes into permutation. 
* 
* The indexes can then be used to permute the objects. 
*/ 
public abstract class PermutationsIterator extends SequenceIterator<List<Integer>> { 

    // Length of the lists required. 
    protected final int length; 
    // The working list. 
    protected final List<Integer> indexes; 

    public PermutationsIterator(int length) { 
     this.length = length; 
     // Build my initial indexes as 0..length 
     indexes = new ArrayList<>(length); 
     for (int i = 0; i < length; i++) { 
      indexes.add(i); 
     } 
     // Start with the initial position. 
     next = Collections.<Integer>unmodifiableList(indexes); 
    } 

    protected abstract boolean nextPerm(); 

    @Override 
    protected List<Integer> getNext() { 
     // Mutate the indexes into the next permutation. 
     if (nextPerm()) { 
      // That's next! 
      return Collections.<Integer>unmodifiableList(indexes); 
     } 
     return null; 
    } 

} 

/** 
* Implements a sequence as an iterator - leaving a getNext() method for the sequence. 
* 
* @param <T> The type that will be iterated over. 
*/ 
public abstract class SequenceIterator<T> implements Iterator<T> { 

    // The next to deliver. 
    protected T next = null; 

    // Return a new next if one is available. 
    protected abstract T getNext(); 

    @Override 
    public boolean hasNext() { 
     if (next == null) { 
      // Is there one? 
      next = getNext(); 
     } 
     return next != null; 
    } 

    @Override 
    public T next() { 
     T n = hasNext() ? next : null; 
     next = null; 
     return n; 
    } 

    @Override 
    public void remove() { 
     throw new UnsupportedOperationException("Cannot remove from sequence"); 
    } 

} 

public void test() { 
    try { 
     for (int l = 0; l < 5; l++) { 
      System.out.println("l = " + l); 
      LexicographicPermutationsIterator lit = new LexicographicPermutationsIterator(l); 
      while (lit.hasNext()) { 
       System.out.println(lit.next()); 
      } 
     } 
    } catch (Throwable t) { 
     t.printStackTrace(System.err); 
    } 
}