Company logo
  • Jobs
  • Bootcamp
  • About Us
  • For professionals
    • Home
    • Jobs
    • Courses
    • Questions
    • Teachers
    • Bootcamp
  • For business
    • Home
    • Our process
    • Plans
    • Assessments
    • Payroll
    • Blog
    • Calculator

0

99
Views
calculate permutation for large number

I am using this java code to try to calculate the permutations of 20: (this is just code part used for calculating permutation)

int[] myArray = new int[20];
for (int i = 0; i < a; i++)
    myArray[i] = i + 1;

List<Integer> intList = new ArrayList<Integer>();
for (int index = 0; index < myArray.length; index++)
{
    intList.add(myArray[index]);
}

List<Integer> vals = intList; 

Collection<List<Integer>> orderPerm = Collections2.permutations(vals);

but of course there is no enough memory for that;

any suggestions?

8 months ago · Santiago Trujillo
3 answers
Answer question

0

There would be 2432902008176640000 of those permutations. http://www.calculatorsoup.com/calculators/discretemathematics/permutations.php?n=20&r=20&action=solve

If you could output 100 000 of permutations per second it would take 2432902008176640000 / 100000 / 60 / 60 / 24 / 365 = 771468 years to do it

100M permutations per second would be faster and take just 771 years

8 months ago · Santiago Trujillo Report

0

The number of permutations of size 20 is 20 factorial, which turns out to be around 10^18. 8 gigabytes of ram are approximately 8 * 10^9 bytes, which as you might understand, is much below the amount of storage needed to store every possible permutations out of the 10^18.

8 months ago · Santiago Trujillo Report

0

Well the less memory approach will involve calculating a fixed but manageable number of permutations on demand. So, you will require a method like getNextPermutation().

I found the method from Collection2.java from Guava's source(the one that you are currently using in your code): https://github.com/google/guava/blob/master/guava/src/com/google/common/collect/Collections2.java

You have,

@Override
    protected List<E> computeNext() {
      if (nextPermutation == null) {
        return endOfData();
      }
      ImmutableList<E> next = ImmutableList.copyOf(nextPermutation);
      calculateNextPermutation();
      return next;
    }

    void calculateNextPermutation() {
      int j = findNextJ();
      if (j == -1) {
        nextPermutation = null;
        return;
      }

      int l = findNextL(j);
      Collections.swap(nextPermutation, j, l);
      int n = nextPermutation.size();
      Collections.reverse(nextPermutation.subList(j + 1, n));
}

You can call this compute next say 100 or 1000 times at once and store the results.

On your part, you will have to fork the source and modify calling of methods here and there a bit to make it as you want.

8 months ago · Santiago Trujillo Report
Answer question
Find remote jobs

Discover the new way to find a job!

Top jobs
Top job categories
Business
Post job Plans Our process Sales
Legal
Terms and conditions Privacy policy
© 2023 PeakU Inc. All Rights Reserved.