# Algorithm suggestion

• August 18th, 2013, 10:42 PM
BlackOwl37
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.
• August 18th, 2013, 11:05 PM
jps
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.
• August 18th, 2013, 11:12 PM
BlackOwl37
Re: Algorithm suggestion
Quote:

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.

Quote:

(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 :-)

Quote:

...and welcome to the forum.
Thanks!
• August 19th, 2013, 12:32 AM
jps
Re: Algorithm suggestion
Quote:

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
• August 19th, 2013, 12:59 AM
helloworld922
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.

Quote:

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?