Хранение перестановки большого числа в базе данных

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)); 


    } 
    } 

Может кто-то пожалуйста, дайте мне знать, могу ли я быть в состоянии решить, если хранить их в базе данных и расчета.

PS: Есть еще один эффективный код, который я могу использовать при поиске 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! Перестановки. Вам понадобится более 6 гигабайт , даже если ваши элементы массива были по 1 байт каждый.

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); 
    } 
}