Welcome to the Java Programming Forums

The professional, friendly Java community. 21,500 members and growing!

The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.

>> REGISTER NOW TO START POSTING

1. ## Algorithm suggestion

I am writing an algorithm to solve what appears to be an NP-complete problem, so naturally I need a brute force algorithm >.< Bearing that in mind, the best solution I have involves an array (wlog) of ints 0-9. I'd like to be able to shuffle those ints around after every step, so that the array reads:

Iteration 1: 0123456789
Iteration 2: 0123456798
then: 0123456879
0123456897
...
9876543210 (which is the final iteration)

Any ideas or pointers?

Complexity is not an issue. I can easily let this program run for ages. Correctness is essential though, so it can be as slow and chunky as it needs so long as it works.

2. ## Re: Algorithm suggestion

Do you have to go through the steps shown above? ...where on the first iteration the last is swapped with the next to last, or can you jump from step 1 to the final output?
Start with what ever solution you can come up with that solves the problem and get it working. If you think it can be improved upon post the code and ask for suggestions.
(we try not to hand out working solutions, but good luck with your project)
...and welcome to the forum.

3. ## Re: Algorithm suggestion

Originally Posted by jps
Do you have to go through the steps shown above? ...where on the first iteration the last is swapped with the next to last, or can you jump from step 1 to the final output?
Hm, no. I don't need to go through every single step in order, but I do need every permutation of the ints 0-9.

(we try not to hand out working solutions, but good luck with your project)
It might be worth pointing out that this is not an assessment for anything academic... but I can still understand not simply handing out solutions :-)

...and welcome to the forum.
Thanks!

4. ## Re: Algorithm suggestion

Originally Posted by BlackOwl37
Hm, no. I don't need to go through every single step in order, but I do need every permutation of the ints 0-9.
0-9 is a large set of numbers to test with, but take a smaller set, and draw up samples. From the samples you should see patterns you can produce in code.

As a limited sample, take 0-2
0-1-2 : 0-2-1 (this is every possibility with 0 as the first digit)
1-0-2 : 1-2-0 (every possibility with 1 first)
2-0-1 : 2-1-0 (and the final sub-set)

Draw out a sample for 0-3, and then 0-4, and so on until the bells and whistles go off

5. ## Re: Algorithm suggestion

I'd hate to just give the answer away, but Google is your friend. Wikipedia: Generate Permutations in Lexicographic Order (the page also has other possible ways to generate permutations). Feel free to ignore this and follow jps's advice if you want to solve the problem for yourself.

Complexity is not an issue. I can easily let this program run for ages. Correctness is essential though, so it can be as slow and chunky as it needs so long as it works.
Be careful what you wish for There are algorithms which won't finish executing before the predicted heat death of the universe.

What is the original problem you want to solve?