Help Needed to Write an Algorithm

Question

Here is a description of the problem

Given an integer N, write a function that returns an integer array of size N containing numbers from 1 to N in random order. Each number from 1 to N should appear once and should not be repeated.

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

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

The invalid conclusions will be 1123, 4444, 244.

Any ideas to solve the problem?

Answer 1

Here's a tip: look at what Fisher-Yates Shuffle is.

Answer 2

, . java, Fisher-Yates shuffle . , . .

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;
}

Answer 3

What you do is shuffle an integer array.

Here is an explanation of Knuth shuffle .