Help needed for writing an algorithm

Question

Here is the description of the the problem

Given an integer N, write a function which returns an integer array of size N, containing the numbers from 1 to N in a random order. Each number from 1 to N must appear once and must not repeat.

• What is the running time of your algorithm?
• Can your algorithm be improved?

For example: if you are given the number 4, your output must generate something like 4213, 2413, 3124, etc.

Invalid outputs would be 1123, 4444, 244.

Any ideas to solve the problem?

Answer 1

Here is a hint: look up what a Fisher-Yates shuffle is.

Answer 2

What you're doing is shuffling an integer array.

Here's an explanation of the Knuth shuffle.

Answer 3

Yes it's home work. I just finished writing the algorithm in java, but using Fisher-Yates shuffle seems to be much more efficient. Thank you people. Below is my version of the algorithm.

Collection<Integer> generateNumbers(int n) {
    Collection<Integer> numbers = new HashSet<Integer>();
    Random rand = new Random();
    int max = 0;        
    int min = 0;
    for(int i=0;i<n;i++){
        max=(max*10)+n;
        min=(min*10)+1;
    }
    while(numbers.size()<n){
        int random = rand.nextInt(max-min+1)+min;
        int temp = random;
        boolean good = true;
        Set<Integer> digits = new HashSet<Integer>();
        while(temp>0 && good){
            int reminder = temp%10;
            if(reminder > 0 && reminder <= n ){ 
                digits.add(reminder);
            }else
                good = false;
            temp/=10;
        }       
        if(good && digits.size() == n)
        numbers.add(random);
    }       
    return numbers;
}