Mixing up a string - Dev Articles

Dev Articles Community Forums Sponsor:

February 9th, 2006, 07:13 PM

highlander2k5

Registered User

Join Date: Sep 2005

Posts: 14

Time spent in forums: 3 h 12 m 31 sec
Reputation Power: 0

Mixing up a string

I was wondering if anyone knew what method to use in order to mix up a user-entered string? For example if the word computer were entered for the string I want it to read something like pmuctreo. Basically it's like a word jumble. Please help... I've been trying to find one on java.sun for hours.

February 10th, 2006, 12:43 AM

Icon

Command Line Warrior

Join Date: Sep 2005

Posts: 633

Time spent in forums: 1 Week 2 Days 5 h 36 m 35 sec
Reputation Power: 3

Pseudocode:

Code:

Create a new empty string (the jumbled result)
Make a list of characters of the entered string
while( not list.isempty)
{
  indexofvictim = Math.Random(list.length)
  Jumbledstring = jumbledstring + list[indexofvictim]
  list.remove(indexofvictim)
}

You can easily create a function like this in any language. There may be easier ways and it's too early for me to remember all the nice java functions out there..

p.s. the pseudo code is very pseudo, i.e., figure out the specifics and off-by-one bugs yourself

Last edited by Icon : February 10th, 2006 at 07:13 AM.

February 10th, 2006, 05:54 AM

destin

Registered User

Join Date: Jan 2006

Posts: 18

Time spent in forums: 1 Day 9 h 6 m 19 sec
Reputation Power: 0

Quote:

Originally Posted by Icon

Pseudocode:
Create a new empty string (the jumbled result)
Make a list of characters of the entered string
while( not list.isempty)
{
indexofvictim = Math.Random(list.length)
Jumbledstring = jumbledstring + list[indexofvictim]
list.remove(indexofvictim)
}

You should use a StringBuffer or StringBuilder here. The way you're doing it you allocate memory for a new String every iteration of the loop.

February 10th, 2006, 07:11 AM

Icon

Command Line Warrior

Join Date: Sep 2005

Posts: 633

Time spent in forums: 1 Week 2 Days 5 h 36 m 35 sec
Reputation Power: 3

highlander2k5 should use something like StringBuffer yes.. As is said: it's just pseudocode, figure the java-specific stuff yourself. There are lots of other ways to jumble a string this was just an example.

Another one comes to mind:

Code:

len = str.length()
for c=0 to len-1
  //swap two chars
  temp = str[c]
  other = random(len)
  str[c] = str[other]
  str[other] = temp

Also jumbles in O(n) ( O(strlen) ) with no extra memory requirements..

The moral is: I don't think something already exists in the Java API, so you have to go nuts yourself

But I might be mistaken, you know of a 'jumble' method destin?

Hmm, I wonder if there are any code obfuscate tools written in Java from which we can get the source...

Comments on this post

MadCowDzz agrees!

February 10th, 2006, 07:19 AM

Icon

Command Line Warrior

Join Date: Sep 2005

Posts: 633

Time spent in forums: 1 Week 2 Days 5 h 36 m 35 sec
Reputation Power: 3

Hmm, you probably need stringbuffer or something for this as well.. Strings are immutable.. I'm doing to many languages at the same time... Of course a good old fashioned char[] would also work..

February 10th, 2006, 07:41 AM

MadCowDzz

I'm Internet Famous

Dev Articles Frequenter (2500 - 2999 posts)

Join Date: Jan 2003

Location: Toronto, Canada

Posts: 2,890

Time spent in forums: 1 Week 16 h 14 m 9 sec
Reputation Power: 8

I like your second example... I'm interested in testing it to see if it works.

__________________
Daryl's Homepage | My Blogroll | My Profile | Firefox supporter!
DevArticles Forum Moderator

"The net is a waste of time, and that's exactly what's right about it." -- William Gibson

February 10th, 2006, 10:24 AM

Icon

Command Line Warrior

Join Date: Sep 2005

Posts: 633

Time spent in forums: 1 Week 2 Days 5 h 36 m 35 sec
Reputation Power: 3

Something like this I guess:

java Code:

Original - java Code

class Jumble
{
  public static String Jumble(String original)
  {
    StringBuilder sb = new StringBuilder(original);
 
    char temp;
    int  swapWith;
    for(int i=0; i<sb.length(); i++)
    {
      temp = sb.charAt(i);
      swapWith = (int)Math.floor(Math.random()*sb.length());
      sb.setCharAt(i, sb.charAt(swapWith));
      sb.setCharAt(swapWith, temp);
    }
 
    return sb.toString();
  }
 
  public static void main(String[] args)
  {
    String someInput = "A nice string";
 
    System.out.println(Jumble(someInput));
    System.out.println(Jumble(someInput));
    System.out.println(Jumble(someInput));
  }
}

This one is actually:
T(n) = 3n ~ O(n)
M(n) = 3n too. Where T is time complexity and M is memory usage (n is, as usual, the length of the problem instance).

Depending on the program one can probably shave of some more cycles but I'm more into understandable code lately

Comments on this post

MadCowDzz agrees: Good code... you beat me to it!

February 10th, 2006, 04:39 PM

highlander2k5

Registered User

Join Date: Sep 2005

Posts: 14

Time spent in forums: 3 h 12 m 31 sec
Reputation Power: 0

Thanks for all the ideas they helped a lot.

February 13th, 2006, 10:18 PM

mrhoo

Registered User

Join Date: Feb 2006

Posts: 4

Time spent in forums: 2 h 17 m 4 sec
Reputation Power: 0

Quote:

Originally Posted by highlander2k5

1. Split the string into an array of characters:
var A=str.split('');

2. pass it to an unsorting function:
A=unsort(A);

3. join the scrambled array with the empty string:
return A.join('');

I scramble a lot of stuff, so I made a scrambler a method of all arrays:

Code:

Array.prototype.disorder=function(){
            var tem,temp;
	var L= this.length;	
	while(--L){
		tem= Math.round(Math.random()*L);
		if(tem!= L){
			temp= this[tem];
			this[tem]= this[L];
			this[L]= temp;
		}
	}
	return this;		
}

Comments on this post

MadCowDzz agrees: Smells like Javascript; not Java... but nice style!

#10

February 14th, 2006, 12:21 AM

Icon

Command Line Warrior

Join Date: Sep 2005

Posts: 633

Time spent in forums: 1 Week 2 Days 5 h 36 m 35 sec
Reputation Power: 3

Nice, but your code looks like Javascript not Java...

#11

February 14th, 2006, 07:30 AM

MadCowDzz

I'm Internet Famous

Join Date: Jan 2003

Location: Toronto, Canada

Posts: 2,890

Time spent in forums: 1 Week 16 h 14 m 9 sec
Reputation Power: 8

Yep, that was Javascript... I like the technique though... good show!

#12

February 14th, 2006, 03:02 PM

destin

Registered User

Join Date: Jan 2006

Posts: 18

Time spent in forums: 1 Day 9 h 6 m 19 sec
Reputation Power: 0

Here's a similar approach to Icon's.

Java Code:

Original - Java Code
public String scramble(String word) { StringBuilder builder = new StringBuilder(word.length()); boolean[] used = new boolean[word.length()]; for (int i = 0; i < word.length(); i++) { int rndIndex; do { rndIndex = new Random().nextInt(word.length()); } while (used[rndIndex]); used[rndIndex] = true; builder.append(word.charAt(rndIndex)); } return builder.toString(); }

public String scramble(String word) {
    StringBuilder builder = new StringBuilder(word.length());
    boolean[] used = new boolean[word.length()];
    
    for (int i = 0; i < word.length(); i++) {
        int rndIndex;
        do {
            rndIndex = new Random().nextInt(word.length());
        } while (used[rndIndex]);
        used[rndIndex] = true;
            
        builder.append(word.charAt(rndIndex));
    }
    return builder.toString();
}

@Icon
swapWith = (int)Math.floor(Math.random()*sb.length());
The Math.floor isn't neccessary:
swapWith = (int) (Math.random() * sb.length());
When casting to an int, it will truncate the end of the double.

Also, you declare [font="Courier New"]temp[/url] and [font="Courier New"]swapWith[/code] outside the loop, but only use them in the loop. It would be better to declare them within the loop; it is best to have variables only declared in the scope they are used in.