Geek Answers Handbook

A faster way to create permutations

I am working on a program that calculates the percentage of hits between two lines (A and B). To get the exact percentage, I match the N-grams with a list of strings that are permutations of string A.

Here is my code

public String[] generatePermutations( String name ){

    String[] perms = new String[ calcN(name.length()) ];
    int nameLen = name.length(),
                cnt = 0;


    for(int i = 0; i < name.length(); i++ ){

        nameLen = name.length()-i;
        for( int ii = 0; ii <= i; ii++){
            perms[cnt++] = name.substring( ii, ii + nameLen );
        }
    }
    return perms;
}

for reference calcN () below

public int calcN( int n ){
    return ( n * (n+1 )) / 2;
}

Given the string "ABC", this method will generate

{"A", "B", "C", "AB", "BC", "ABC"}

Since I do this operation thousands of times (maybe hundreds of thousands), is there a way to compress a few extra loops from my processor? (besides switching to C ++ or C). As always, in advance for a consultation!

+4
3

JVM. , OpenJDK :

public String substring(int beginIndex, int endIndex) {
    if (beginIndex < 0) {
        throw new StringIndexOutOfBoundsException(beginIndex);
    }
    if (endIndex > count) {
        throw new StringIndexOutOfBoundsException(endIndex);
    }
    if (beginIndex > endIndex) {
        throw new StringIndexOutOfBoundsException(endIndex - beginIndex);
    }
    return ((beginIndex == 0) && (endIndex == count)) ? this :
        new String(offset + beginIndex, endIndex - beginIndex, value);
}

, :

 // Package private constructor which shares value array for speed.
String(int offset, int count, char value[]) {
     this.value = value;
     this.offset = offset;
     this.count = count;
 }

, (char [], String).

, Java 7, - ( 1000 , , 1000 , ).

, , jvm , .

, , String, .

+1

, , , , .

Scala :

(1 to 3).flatMap("ABC".combinations(_))


Vector(A, B, C, AB, AC, BC, ABC)


"ABC".permutations.toList


List(ABC, ACB, BAC, BCA, CAB, CBA)

Scala JVM.

+1

This would not help, but I do not see the use cntthat just useii

0
source

More articles:


All Articles