Over a million developers have joined DZone.

Java 8 String Unique Permutations in Parallel

Here's an awesome snippet for Java 8 string unique permutations running in parallel!

· Java Zone

Check out this 8-step guide to see how you can increase your productivity by skipping slow application redeploys and by implementing application profiling, as you code! Brought to you in partnership with ZeroTurnaround.

Here is the code for 20 as the length limit otherwise it needs memory. For no memory problems code go below:

package com.bos;

import java.util.Date;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class StringPermutation {
public static Stream<String> permutations(String str) {
if (str.isEmpty()) {
return Stream.of("");
}
return IntStream.range(0, str.length()).boxed()
.flatMap(i -> permutations(str.substring(0, i) + str.substring(i + 1)).map(t -> str.charAt(i) + t));
}

public static void main(String[] args) {
Date startDate = new Date();
long startTime = System.nanoTime();
System.out.println("Started at " + startDate);
permutations("ferrao").parallel().collect(Collectors.toSet()).stream().sorted().forEach(System.out::println);
Date endDate = new Date();
long totalTime = System.nanoTime() - startTime;
System.out.println("Ended at " + endDate + " total time=" + totalTime + " nanosec");
}
}

For the word "ferrao" this gives unique 360 all combinations(if toSet() not made one can get 720 all combinations):

aeforr
aefror
aefrro
aeofrr
aeorfr
aeorrf
aerfor
aerfro
aerofr
aerorf
aerrfo
aerrof
afeorr
aferor
aferro
afoerr
aforer
aforre
afreor
afrero
afroer
afrore
afrreo
afrroe
aoefrr
aoerfr
aoerrf
aoferr
aofrer
aofrre
aorefr
aorerf
aorfer
aorfre
aorref
aorrfe
arefor
arefro
areofr
areorf
arerfo
arerof
arfeor
arfero
arfoer
arfore
arfreo
arfroe
aroefr
aroerf
arofer
arofre
aroref
arorfe
arrefo
arreof
arrfeo
arrfoe
arroef
arrofe
eaforr
eafror
eafrro
eaofrr
eaorfr
eaorrf
earfor
earfro
earofr
earorf
earrfo
earrof
efaorr
efaror
efarro
efoarr
eforar
eforra
efraor
efraro
efroar
efrora
efrrao
efrroa
eoafrr
eoarfr
eoarrf
eofarr
eofrar
eofrra
eorafr
eorarf
eorfar
eorfra
eorraf
eorrfa
erafor
erafro
eraofr
eraorf
erarfo
erarof
erfaor
erfaro
erfoar
erfora
erfrao
erfroa
eroafr
eroarf
erofar
erofra
eroraf
erorfa
errafo
erraof
errfao
errfoa
erroaf
errofa
faeorr
faeror
faerro
faoerr
faorer
faorre
fareor
farero
faroer
farore
farreo
farroe
feaorr
fearor
fearro
feoarr
feorar
feorra
feraor
feraro
feroar
ferora
ferrao
ferroa
foaerr
foarer
foarre
foearr
foerar
foerra
foraer
forare
forear
forera
forrae
forrea
fraeor
fraero
fraoer
fraore
frareo
fraroe
freaor
frearo
freoar
freora
frerao
freroa
froaer
froare
froear
froera
frorae
frorea
frraeo
frraoe
frreao
frreoa
frroae
frroea
oaefrr
oaerfr
oaerrf
oaferr
oafrer
oafrre
oarefr
oarerf
oarfer
oarfre
oarref
oarrfe
oeafrr
oearfr
oearrf
oefarr
oefrar
oefrra
oerafr
oerarf
oerfar
oerfra
oerraf
oerrfa
ofaerr
ofarer
ofarre
ofearr
oferar
oferra
ofraer
ofrare
ofrear
ofrera
ofrrae
ofrrea
oraefr
oraerf
orafer
orafre
oraref
orarfe
oreafr
orearf
orefar
orefra
oreraf
orerfa
orfaer
orfare
orfear
orfera
orfrae
orfrea
orraef
orrafe
orreaf
orrefa
orrfae
orrfea
raefor
raefro
raeofr
raeorf
raerfo
raerof
rafeor
rafero
rafoer
rafore
rafreo
rafroe
raoefr
raoerf
raofer
raofre
raoref
raorfe
rarefo
rareof
rarfeo
rarfoe
raroef
rarofe
reafor
reafro
reaofr
reaorf
rearfo
rearof
refaor
refaro
refoar
refora
refrao
refroa
reoafr
reoarf
reofar
reofra
reoraf
reorfa
rerafo
reraof
rerfao
rerfoa
reroaf
rerofa
rfaeor
rfaero
rfaoer
rfaore
rfareo
rfaroe
rfeaor
rfearo
rfeoar
rfeora
rferao
rferoa
rfoaer
rfoare
rfoear
rfoera
rforae
rforea
rfraeo
rfraoe
rfreao
rfreoa
rfroae
rfroea
roaefr
roaerf
roafer
roafre
roaref
roarfe
roeafr
roearf
roefar
roefra
roeraf
roerfa
rofaer
rofare
rofear
rofera
rofrae
rofrea
roraef
rorafe
roreaf
rorefa
rorfae
rorfea
rraefo
rraeof
rrafeo
rrafoe
rraoef
rraofe
rreafo
rreaof
rrefao
rrefoa
rreoaf
rreofa
rrfaeo
rrfaoe
rrfeao
rrfeoa
rrfoae
rrfoea
rroaef
rroafe
rroeaf
rroefa
rrofae
rrofea

This code doesn't have memory problems for all combinations of string:

Maven configuration:

<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
<modelVersion>4.0.0</modelVersion>
<groupId>com.bos</groupId>
<artifactId>bosproj</artifactId>
<version>0.0.1-SNAPSHOT</version>
<name>bosproj</name>

<dependencies>
        <dependency>
<groupId>org.apache.derby</groupId>
<artifactId>derby</artifactId>
<version>10.12.1.1</version>
</dependency>
 <dependency>
            <groupId>org.apache.derby</groupId>
            <artifactId>derbyclient</artifactId>
            <version>10.12.1.1</version>
        </dependency>
        <dependency>
            <groupId>org.apache.derby</groupId>
            <artifactId>derbynet</artifactId>
            <version>10.12.1.1</version>
        </dependency>
        <dependency>
            <groupId>org.apache.derby</groupId>
            <artifactId>derbytools</artifactId>
            <version>10.12.1.1</version>
        </dependency>
</dependencies>

<build>
<plugins>
<plugin>
<groupId>org.apache.maven.plugins</groupId>
<artifactId>maven-compiler-plugin</artifactId>
<version>3.5</version>
<configuration>
<!-- or whatever version you use -->
<source>1.8</source>
<target>1.8</target>
</configuration>
</plugin>
</plugins>
</build>
</project>

The Java code is here:

package com.bos;

import java.math.BigInteger;
import java.sql.Connection;
import java.sql.DriverManager;
import java.sql.PreparedStatement;
import java.sql.ResultSet;
import java.util.Date;
import java.util.concurrent.atomic.AtomicReference;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class StringPermutation {
private static Connection connect = null;
private static PreparedStatement statement = null;
private static ResultSet resultSet = null;

private static AtomicBigInteger count = new AtomicBigInteger(new BigInteger("-1"));

static class Pair {
final BigInteger num;
final BigInteger value;

Pair(BigInteger num, BigInteger value) {
this.num = num;
this.value = value;
}
}

public static BigInteger factorial(BigInteger num) {
Stream<Pair> allFactorials = Stream.iterate(new Pair(BigInteger.ONE, BigInteger.ONE),
x -> new Pair(x.num.add(BigInteger.ONE), x.value.multiply(x.num.add(BigInteger.ONE))));
return allFactorials.filter((x) -> x.num.equals(num)).findAny().get().value;
}

public static void stringPermutations(String str) {
try {
String DB_NAME = "StringPermutationsDb";
int number = str.length();
Class.forName("org.apache.derby.jdbc.ClientDriver").newInstance();
connect = DriverManager.getConnection("jdbc:derby://localhost/" + DB_NAME + ";create=true");
try {
statement = connect.prepareStatement("drop table keyValue");
statement.execute();
} catch (Exception e) {
System.out.println("Ignore the following exception:");
e.printStackTrace();
} finally {
closeNotConnection();
}
statement = connect
.prepareStatement("create table keyValue(keyName LONG VARCHAR, value VARCHAR(" + number + "))");
statement.execute();
statement.close();

statement = connect.prepareStatement("insert into keyValue values (?, ?)");
BigInteger max = factorial(new BigInteger(String.valueOf(number)));
System.out.println("Combinations of " + number + "=" + max.toString() + " for " + str);
permutation(str);
statement.executeBatch();
statement.close();

BigInteger curMax = max.divide(BigInteger.TEN);
curMax = (max.remainder(BigInteger.TEN).compareTo(BigInteger.ZERO) > 0) ? curMax.add(BigInteger.ONE)
: curMax;

for (BigInteger i = BigInteger.ZERO; i.compareTo(curMax) < 0; i = i.add(BigInteger.ONE)) {
statement = connect.prepareStatement("select * from keyValue order by value offset "
+ i.multiply(BigInteger.TEN).toString() + " rows fetch first 10 rows only");
resultSet = statement.executeQuery();
while (resultSet.next()) {
String keyName = resultSet.getString("keyName");
String value = resultSet.getString("value");
System.out.println("key: " + keyName + " value:" + value);
}
closeNotConnection();
}
} catch (Exception e) {
e.printStackTrace();
} finally {
close();
}

}

public static void permutation(String str) throws Exception {
permutation("", str);
}

private static void permutation(String prefix, String str) throws Exception {
int n = str.length();
if (n == 0) {
BigInteger cnt = count.incrementAndGet();
statement.setString(1, cnt.toString());
statement.setString(2, prefix);
statement.addBatch();
if (cnt.compareTo(BigInteger.ZERO) > 0 && cnt.remainder(new BigInteger("1000")).equals(BigInteger.ZERO)) {
statement.executeBatch();
System.out.println(cnt + " are done...");
}
} else {
IntStream.range(0, n).parallel().forEach(i -> {
try {
permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n));
} catch (Exception e) {
e.printStackTrace();
}
});

}
}

static final class AtomicBigInteger {
private final AtomicReference<BigInteger> valueHolder = new AtomicReference<>();

public AtomicBigInteger(BigInteger bigInteger) {
valueHolder.set(bigInteger);
}

public BigInteger incrementAndGet() {
for (;;) {
BigInteger current = valueHolder.get();
BigInteger next = current.add(BigInteger.ONE);
if (valueHolder.compareAndSet(current, next)) {
return next;
}
}
}
}

private static void closeNotConnection() {
try {
if (resultSet != null) {
resultSet.close();
}
if (statement != null) {
statement.close();
}
} catch (Exception e) {

}
}

private static void close() {
try {
if (resultSet != null) {
resultSet.close();
}
if (statement != null) {
statement.close();
}
if (connect != null) {
connect.close();
}
} catch (Exception e) {

}
}

public static void main(String[] args) {
int rangeLow = 65;
int number = 5;

Date startDate = new Date();
long startTime = System.nanoTime();
System.out.println("Started at " + startDate);
// commented for out of memory
// permutations(IntStream.range(0, number).boxed().map(s ->
// Character.toString((char) (rangeLow + s)))
// .collect(Collectors.toList()).stream().map(i -> i).reduce((a, b) -> a
// + b).get()).parallel()
// .collect(Collectors.toSet()).stream().sorted().forEach(System.out::println);

// stringPermutations(IntStream.range(0, number).boxed().map(s ->
// Character.toString((char) (rangeLow + s)))
// .collect(Collectors.toList()).stream().map(i -> i).reduce((a, b) -> a
// + b).get());

stringPermutations(IntStream.range(rangeLow, rangeLow + number).mapToObj(c -> String.valueOf((char) c))
.collect(Collectors.joining()));

Date endDate = new Date();
long totalTime = System.nanoTime() - startTime;
System.out.println("Ended at " + endDate + " total time=" + totalTime + " nanosec");
}
}

For the code above:

Combinations of 27=10888869450418352160768000000 for ABCDEFGHIJKLMNOPQRSTUVWXYZ[

should work fine with Apache Derby DB. After checking for 44 minutes it does 126603000 with 7.82 GB disk space will take 2628021890709143143.186 days on my PC.

Limitation of LONG VARCHAR and VARCHAR of Apache Derby Data Types. Please let me know of any futher limitations.

The Java Zone is brought to you in partnership with ZeroTurnaround. Check out this 8-step guide to see how you can increase your productivity by skipping slow application redeploys and by implementing application profiling, as you code!

Topics:
java 8 ,string ,parallel

Opinions expressed by DZone contributors are their own.

The best of DZone straight to your inbox.

SEE AN EXAMPLE
Please provide a valid email address.

Thanks for subscribing!

Awesome! Check your inbox to verify your email so you can start receiving the latest in tech news and resources.
Subscribe

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}