Member Avatar for Dark_Omen

Hi, i was writing a program to make permutations of strings, but I ran into a snag and can't figure out what's wrong. It prints out the permutated strings, but some of them are duplicates.
I attached the source
Thanks for the help.

import java.util.*;

public class ArrayUtils {
	public void arrayShuffle(int[] array){
		Random rand = new Random();
		int k, n, tmp;
		for(int i = 0; i < 5 * array.length; i++){
			k = rand.nextInt(array.length);
			n = rand.nextInt(array.length);
			tmp = array[k];
			array[k] = array[n];
			array[n] = tmp;
		}
	}
}
public class StringPerm {
 private String word;
 private int wordLength;
 private int numOfPerms;
 private String[] permWords;
 private int[] storeNums;
 private int[] tmpArray;
 private int[][] permNums;
 private int count = 0;
 
 public StringPerm(String word){
  this.word = word;
  wordLength = word.length();
  numOfPerms = numberOfPermutations(wordLength);
  permWords = new String[numOfPerms];
  permNums = new int[numOfPerms][wordLength];
  storeNums = new int[wordLength];
  for(int i = 0; i < storeNums.length; i++){
	  storeNums[i] = i;
  }
 }
 
 public void makePermutations(){
	 ArrayUtils au = new ArrayUtils();
	 tmpArray = storeNums;
	 //for(int i = 0; i < numOfPerms; i++){
	 while(count < numOfPerms){
		 if(!isNew(tmpArray)){ 
			 au.arrayShuffle(tmpArray);
			 append(tmpArray);
		 }
		 count++;
	 }
	 printPermutations();
 }

 public void append(int[] array){
	 String tmpString = "";
	 //add the numbers into permNums for later testing
	 for(int i = 0; i < array.length; i++){
		 permNums[count][i] = array[i];
	 }
	 //take the number from the array passed in to be used to find the word
	 for(int k = 0; k < array.length; k++){
		 tmpString = tmpString + word.charAt(array[k]) + "";
	 }
	 permWords[count] = tmpString;
	 //add the word to permWords
 }
 
 public boolean isNew(int[] array){
	 boolean isNew = true;
	 for(int i = 0; i < numOfPerms; i++){
		 for(int k = 0; k < wordLength; k++){
			 if(permNums[i][k]== array[k]){
				 return isNew = false;
			 }
		 }
	 }
	 return isNew;
 }
 
 public int numberOfPermutations(int length){
  int total = length;
  for (int i = length - 1; i > 0; i--){
   total *= i;
  }
  return total;
 }
 
 public void printPermutations(){
	 for(int i = 0; i < numOfPerms; i++){
		 System.out.println(permWords[i]);
	 }
 }
}
import java.util.*;

public class StringPermDriver {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		String myStr = scan.next();
		StringPerm strperm = new StringPerm(myStr);
		strperm.makePermutations();
	}
}
  • 3 Contributors
  • 3 Replies
  • 132 Views
  • 1 Week Discussion Span
  • Latest Post Latest Post by Dark_Omen

Recommended Answers

All 3 Replies

Member Avatar for server_crash

Since you are using arraylist, use the contains() method to check if the entry already exists. If it doesn't, then add it.

Member Avatar for Dark_Omen

I actually found a better way to do this problem, less chaotic as the way I was doing it.
Here is the source for it:

public class StringPerm {
 private int count = -1;
 private int numOfPerms;
 private String word;
 private int stringLength;
 private int[] permNums;
 private String[] permWords;
 private int permWordsCt = 0;
 
 
 public StringPerm(String word) {
  this.word = word;
  stringLength = word.length();
  numOfPerms = numberOfPermutations(stringLength);
  permNums = new int[stringLength];
  permWords = new String[numOfPerms];
 }
 
 public void makePermutations(int characterPos) {
  count++;
  permNums[characterPos] = count;
  
  if (count == stringLength) {
   append();
  }
  else {
   for (int i=0; i<stringLength; i++) {
	if (permNums[i] == 0) {
	 makePermutations(i);
	}
   }
  }
  count--;
  permNums[characterPos] = 0;
  }
 
 public void append(){
  String tmpWord = "";
  for (int i = 0; i < stringLength; i++) {
   tmpWord = tmpWord + word.charAt(permNums[i] - 1);
  }
  if(permWordsCt < numOfPerms){
   permWords[permWordsCt] = tmpWord;
   permWordsCt++;
  }
 }
 
 public void printPermutations(){
   for(int i = 0; i < numOfPerms; i++){
	System.out.println(permWords[i]);
   }
  }
 
 public int numberOfPermutations(int length){
   int total = length;
   for (int i = length - 1; i > 0; i--){
	total *= i;
   }
   return total;
  }
}

Thanks for the ideas though.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.