How to decrese permutation time?

Question

I don't really hope to get an answer but I think of this more like a brainstorm so give you're best idea please :)

So I want to make a program that makes permutations of all the ASCII characters, and I can't connect 1000 computer to calculate this because unfortunately I have only one computer so I need some kind of algorithm to speed up the process.

I made the algorithm to find the possible combinations but I look online and it will take more then 100 years. PLEASE HELP.

This is the code to find permutations (it doesn't find all ASCII character permutations, but has a string with all letters and numbers and from that string he makes the permutations):

import java.io.*;

public class doIt extends AI {

    public void check() {
        String letters = "qwertzuioplkjhgfdsayxcvbnm0123456789-_";
        permute(letters);

    }

    public void permute(String letters) {

        int length = letters.length();
        boolean[] used = new boolean[length];
        StringBuffer str = new StringBuffer(length);

        permutation(str, letters, used, length, 0);
    }

    public void permutation(StringBuffer str, String letters, boolean[] used, int length, int position) {

        if (position == length) {
            try {
                File one = new File("G:/AllDateBases/Combinations.txt");
                PrintWriter pw = new PrintWriter(new FileWriter("G:/AllDateBases/Combinations.txt", true));
                pw.println(str.toString());
                pw.close();
            } catch (IOException e) {
                System.out.println("Error");
            }
            return;
        } else {
            for (int i = 0; i < length; i++) {

                if (used[i]) continue;

                str.append(letters.charAt(i));
                used[i] = true;

                permutation(str, letters, used, length, position + 1);

                str.deleteCharAt(str.length() - 1);
                used[i] = false;
            }
        }
    }
}

That behavior is generally the case with unbounded permutations. Can we see what you've done? — Ryan Jackman, Jul 14 '15 at 19:20
Note: don't try to write more than one line in the comments, and avoid trying to paste code in them. All additional information should go as edit to the original question. — RealSkeptic, Jul 14 '15 at 19:25
ReakSkeptic thanks I'm new here so I don't know how it works :) — Not_Important, Jul 14 '15 at 19:27
Well if you enumerate n! permutations, then it will necessarily take ages. But why would you want to do that? What problem are you trying to solve? — user140547, Jul 14 '15 at 19:32
Have you succeeded in running your program to its completion? — RealSkeptic, Jul 14 '15 at 19:32
There is not a real problem that I 'm trying to solve just wont to see if somebody has some idea on how to speed up the process — Not_Important, Jul 14 '15 at 19:34
[This question](http://stackoverflow.com/questions/1995328/are-there-any-better-methods-to-do-permutation-of-string) has some good discussion about permutation algorithms. Unfortunately, there are 38! permutations of that string and the collective storage space of mankind could not hold it. — Ryan Jackman, Jul 14 '15 at 19:42
Well you could try to make minor optimizations or try to parallelize it, but nevertheless it it is not feasible to print (if I get the math right) 38! ~ 10^44 strings and expect it to terminate in a reasonable timescale — user140547, Jul 14 '15 at 19:42
I am not planinig to save all the permutation(inthe code it saves it on a file but thats not the problem right now) just wont to find a way(if it is possible) to do it — Not_Important, Jul 14 '15 at 20:01
If you had a CPU which could process 10^20 instructions per second, and if one instruction is enough to process one permutation, it could only process 10^20*86400*365*100 ~ 10^30 permutations in 100 years, but you want to process ~10^44 permutations. So it is just not feasible. — user140547, Jul 14 '15 at 20:09
If you are using this to simulate a brute force attack in your pen testing, consider using a precompiled rainbow table or other type of prepackaged pw list. No need to reinvent the wheel. — Andreas, Jul 14 '15 at 21:39
It is possible to generate one permutation of n things in O(n) time and to do this uniquely for each of the n! permutations as a function of i in 1 to n!, which effectively provides them on demand. See http://antoinecomeau.blogspot.ca/2014/07/mapping-between-permutations-and.html — , Jul 14 '15 at 23:06

score 0 · Accepted Answer · answered Jul 14 '15 at 20:16

0

Going through permutations takes a long time. When solving problems that require looking through all the possible solutions, there are often ways to cut out many permutations, or interesting algorithms to get a solution faster.

Here's an example of a problem like this: https://projecteuler.net/problem=67 trying all the combinations is impossible (it would take a computer 20 billion years). But using an interesting algorithm, the problem can be solved in under a second.

answered Jul 14 '15 at 20:16

dustinevan

918
9
21

True, however it is possible to generate one permutation in O(n) and to do this uniquely for each of the n! as a function of i in 1 to n! using Lehmer codes, which effectively provides them on demand. See http://antoinecomeau.blogspot.ca/2014/07/mapping-between-permutations-and.html and https://en.wikipedia.org/wiki/Lehmer_code. – Jul 14 '15 at 23:09

How to decrese permutation time?

1 Answers1