Click here to Skip to main content
15,884,388 members
Please Sign up or sign in to vote.
2.33/5 (2 votes)
See more:
Hello everybody!

I would like to ask some help regarding one swap algorithm I am doing. The algorithm need to swap all elements of the array with every possible combination of the elements of it. I am stuck trying to get the best possible time complexity for this algorithm, but I cannot do better than O(N raised to 2). I am running out of ideas. The algorithm I have is the following:

Code:
import java.math.*;


class SwapAlgo {
    public int main(int[] A) {
        int l=0,k=0;
        


            //Swap algorithm
            for (l=0 ; l < A.length ; l++){
                for (k = l+1 ; k < A.length ; k++){


                    int [] A_aux = A;
                    int num_aux = A_aux[l];
                    A_aux [l] = A_aux[k];
                    A_aux[k]=num_aux;
                    
             }
     }
}


My question is, is there any swap algorithm with better time complexity? In this case O(N).

Thank you very much!

[EDIT: Matt T Heffron -- moved up from improper "Solution"]
Thankls for the reply.

What I ment about "swap all elements of the array with every possible combination of the elements of it" is, for example, having array [3,-6,2,1]

I want to swap every element with in every possible way, that means:

Swap element in the position 0 with element in the position 1 (3,-6)
Swap element in the position 0 with element in the position 2 (3, 2)
Swap element in the position 0 with element in the position 3 (3, 1)
Swap element in the position 1 with element in the position 2 (-6, 2)
Swap element in the position 1 with element in the position 3 (-6, 1)
And the last swap element in the position 2 with element in the position 3 (2, 1)

For that I need to do two loops in order to check the array (like I am doing in the program). What Im asking if there is any more optimal way in order to achieve a O(N) time complexity (mine is O(N2) because the two loops for.

Thanks
Posted
Updated 12-Jun-14 8:06am
v3
Comments
Sergey Alexandrovich Kryukov 11-Jun-14 17:37pm    
First of all, you need to define what you need to achieve formally and strictly. Your "swap all elements of the array with every possible combination of the elements of it" is somewhat ambiguous. What is that "combination"?
Do you want to get all permutations? But just the number of them (forget about the algorithm) is N!. What are you talking about?
—SA
OmarLittle70 12-Jun-14 11:05am    
Thanks for the reply.

What I ment about "swap all elements of the array with every possible combination of the elements of it" is, for example, having array [3,-6,2,1]

I want to swap every element with in every possible way, that means:

Swap element in the position 0 with element in the position 1 (3,-6)
Swap element in the position 0 with element in the position 2 (3, 2)
Swap element in the position 0 with element in the position 3 (3, 1)
Swap element in the position 1 with element in the position 2 (-6, 2)
Swap element in the position 1 with element in the position 3 (-6, 1)
And the last swap element in the position 2 with element in the position 3 (2, 1)

For that I need to do two loops in order to check the array (like I am doing in the program). What Im asking if there is any more optimal way in order to achieve a O(N) time complexity (mine is O(N2) because the two loops for.

Thanks
Matt T Heffron 12-Jun-14 14:13pm    
As Sergey suspected you want all of the permutations.
This cannot be done in O(N) or even O(N^2).
This is O(N!).
http://en.wikipedia.org/wiki/Permutation

1 solution

Try running the program with the input array the numbers 1 through 9, and look at the result.
I think the optimization will be obvious how to make it O(N).
 
Share this answer
 
Comments
phil.o 12-Jun-14 18:38pm    
A permutation algorithm in O(N)? You really should write an article on the obvious.
Matthew Dennis 15-Jun-14 16:58pm    
All this code does is reverse the order of the elements in the array. A simple O(N) operation.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900