Solved

Scrambler letters / all possible combinations

Posted on 2006-05-30
1,465 Views
Hello,

I need a function that Scrambles words... I pass in "this" and it returns an ArrayList like this:

this
hist
isth
sthi
thsi
hits
isth
stih
htsi
ihts
sith
tsih

So it just returns every possible combination for that word(s). (and should work for any number of letters)
0
Question by:JoshWegener

LVL 2

Expert Comment

This sounds like you are fishing for an algorithm to turn in for a homework assignment.
0

LVL 1

Author Comment

Nope... I encrypted XLS sheets (Holding all of my account numbers/user nams/passwords and so on) and I forgot my dang password to open the file.... but I aways use the same letters/numbers in my password... (I just forgot what order) So I am going to run this against the encryption program and try to get my data back.
0

LVL 2

Accepted Solution

From http://www.merriampark.com/comb.htm

Introduction

The CombinationGenerator Java class systematically generates all combinations of n elements, taken r at a time. The algorithm is described by Kenneth H. Rosen, Discrete Mathematics and Its Applications, 2nd edition (NY: McGraw-Hill, 1991), pp. 284-286.

The class is very easy to use. Suppose that you wish to generate all possible three-letter combinations of the letters "a", "b", "c", "d", "e", "f", "g". Put the letters into an array. Keep calling the combination generator's getNext () method until there are no more combinations left. The getNext () method returns an array of integers, which tell you the order in which to arrange your original array of letters. Here is a snippet of code which illustrates how to use the CombinationGenerator class.

String[] elements = {"a", "b", "c", "d", "e", "f", "g"};
int[] indices;
CombinationGenerator x = new CombinationGenerator (elements.length, 3);
StringBuffer combination;
while (x.hasMore ()) {
combination = new StringBuffer ();
indices = x.getNext ();
for (int i = 0; i < indices.length; i++) {
combination.append (elements[indices[i]]);
}
System.out.println (combination.toString ());
}

Another example of the usage of the CombinationGenerator is shown below in connection with the Zen Archery problem.

Source Code
The source code is free for you to use in whatever way you wish.

//--------------------------------------
// Systematically generate combinations.
//--------------------------------------

import java.math.BigInteger;

public class CombinationGenerator {

private int[] a;
private int n;
private int r;
private BigInteger numLeft;
private BigInteger total;

//------------
// Constructor
//------------

public CombinationGenerator (int n, int r) {
if (r > n) {
throw new IllegalArgumentException ();
}
if (n < 1) {
throw new IllegalArgumentException ();
}
this.n = n;
this.r = r;
a = new int[r];
BigInteger nFact = getFactorial (n);
BigInteger rFact = getFactorial (r);
BigInteger nminusrFact = getFactorial (n - r);
total = nFact.divide (rFact.multiply (nminusrFact));
reset ();
}

//------
// Reset
//------

public void reset () {
for (int i = 0; i < a.length; i++) {
a[i] = i;
}
numLeft = new BigInteger (total.toString ());
}

//------------------------------------------------
// Return number of combinations not yet generated
//------------------------------------------------

public BigInteger getNumLeft () {
return numLeft;
}

//-----------------------------
// Are there more combinations?
//-----------------------------

public boolean hasMore () {
return numLeft.compareTo (BigInteger.ZERO) == 1;
}

//------------------------------------
//------------------------------------

public BigInteger getTotal () {
}

//------------------
// Compute factorial
//------------------

private static BigInteger getFactorial (int n) {
BigInteger fact = BigInteger.ONE;
for (int i = n; i > 1; i--) {
fact = fact.multiply (new BigInteger (Integer.toString (i)));
}
return fact;
}

//--------------------------------------------------------
// Generate next combination (algorithm from Rosen p. 286)
//--------------------------------------------------------

public int[] getNext () {

if (numLeft.equals (total)) {
numLeft = numLeft.subtract (BigInteger.ONE);
return a;
}

int i = r - 1;
while (a[i] == n - r + i) {
i--;
}
a[i] = a[i] + 1;
for (int j = i + 1; j < r; j++) {
a[j] = a[i] + j - i;
}

numLeft = numLeft.subtract (BigInteger.ONE);
return a;

}
}
0

Expert Comment

what if I wanted abc ,bca, acb and so on in the combination
0

Featured Post

Suggested Solutions

Need some clarity on Rest API 5 51
array6 challenfge 6 48
strDist challenge 35 69
word0 challenge 3 28
For customizing the look of your lightweight component and making it look opaque like it was made of plastic.  This tip assumes your component to be of rectangular shape and completely opaque.   (CODE)
Java had always been an easily readable and understandable language.  Some relatively recent changes in the language seem to be changing this pretty fast, and anyone that had not seen any Java code for the last 5 years will possibly have issues unde…
Viewers learn about the third conditional statement “else if” and use it in an example program. Then additional information about conditional statements is provided, covering the topic thoroughly. Viewers learn about the third conditional statement …
This tutorial explains how to use the VisualVM tool for the Java platform application. This video goes into detail on the Threads, Sampler, and Profiler tabs.