Помощь требуется для написания алгоритма

Question

Здесь описание проблемы

Дано целое число N, написать функцию, которая возвращает целочисленный массив размера N, содержащий числа от 1 до N в случайном порядке. Каждое число от 1 до N должно появляться один раз и не должно повторяться.

• Каково время вашего алгоритма?
• Может ли ваш алгоритм быть улучшен?

Например: если вы получаете номер 4, ваш выход должен генерировать что-то вроде 4213, 2413, 3124 и т.д.

инвалидных выходы будут 1123, 4444, 244.

Любого идеи для решения проблемы?

Answer 1

Подсказка: посмотрите, что такое Shisher-Fisher-Yates.

Answer 2

Что вы делаете, это перетасовка целочисленного массива.

Приведено описание модели Knuth shuffle.

Answer 3

Да, это работа на дому. Я только что закончил писать алгоритм в 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; 
}