Понимание массива Заполнение случайных чисел (Big Java Ex 7,4)

Question

Постановка задачи

Напишите программу, которая производит случайные перестановки чисел от 1 до 10. Для того, чтобы сгенерировать случайную перестановку, вам необходимо заполнить массив с номерами от 1 до 10, так что никакие две записи массива не имеют одинакового содержимого . Вы можете сделать это с помощью грубой силы, вызвав Random.nextInt , пока не выдает значение, которое еще не находится в массиве. Вместо этого вы должны использовать интеллектуальный метод, . Сделайте второй массив и заполните его с номерами от 1 до 10. Затем выберите один из них случайным образом, удалите его, и добавьте его в массив перестановок. Повторите 10 раз. Реализовать класс PermutationGenerator с методом междунар [] nextPermutation

У меня возникли некоторые проблемы с пониманием того, что вопрос говорит.

Мое толкование заключается в том, что нам нужно поместить числа 1-10 в массив, учитывая некоторые случайные числа, которые могут варьироваться от одного до десяти.

Как я могу решить это, просто добавив массив и выполнив цикл и просто проверив, находится ли следующее случайное число в массиве. Однако в соответствии с вопросом это считается «грубой силой»

Я не совсем уверен, что говорит моя книга, реализуя второй массив. Если я сделаю второй массив, мне все равно придется проверять, находится ли что-то в массиве?

Моя попытка Во-первых, я просто пытаюсь поставить 10 случайных чисел в массив, и игнорируя часть о том, что они должны быть различны. Вот что у меня есть

private int[] arr; 
private Random randNum; 

public seq() 
{ 
    randNum = new Random(); 
    arr = new int[10]; 
} 

public int getRandNum() 
{ 
    int newNum = randNum.nextInt(10)+1; 
    return newNum; 
} 

public int [] filledArr() 
{ 
    for (int i = 0 ; i<arr.length; i++) 
    { 
     arr[i] = getRandNum(); 
    } 
    return arr; 
} 

Проблема с этим состоит в том, что я должен был бы назвать getRandNum() 10 раз, чтобы получить 10 различных чисел, а затем вызвать filledArr положить его внутрь. Это ALOT ввода. Есть ли способ лучше? Наверное, я мог бы сделать цикл for внутри main и сделать это? Это кажется ужасно неэффективным.

Спасибо за любые советы

Другой Попытка

class seq 
{ 
    private int[] arr; 
    private int[] filledArr; 
    private Random randNum; 

    public seq() 
    { 
     randNum = new Random(); 
     arr = new int[10]; 
     filledArr = new int[10]; 
    } 

    public int [] generateNewArr() 
    { 
     for(int i = 1; i< 11 ; i++) 
     { 
      filledArr[i] = i; 
     } 
     return filledArr; 
    } 

    public int [] newArr() 
    { 
     for(int i=1; i < 11 ; i++) 
     { 
      int newRandNum = //RANDOM NUMBER IN filledArr; 
      arr[i] = newRandNum; 
      // REMOVE that random number from filledArr 
     } 
    } 

} 

ПОПЫТКА С ArrayLists

import java.util.Random; 
import java.util.ArrayList; 
class seq 
{ 
    private ArrayList<Integer> arrListOne; 
    private ArrayList<Integer> arrListTwo; 
    private Random num; 
    public seq() 
    { 
     num = new Random(); 
     arrListOne = new ArrayList<Integer>(10); 
     arrListTwo = new ArrayList<Integer>(10); 
    } 
    public ArrayList getFilledArr() 
    { 
     for(int i = 1; i < arrListOne.size()+1 ; i++) 
     { 
      arrListOne.add(i); 
     } 
     return arrListOne; 
    } 
    public ArrayList randNewArr() 
    { 
     for(int i = 0 ; i < 10 ; i++) 
     { 
     int randNum = num.nextInt(arrListOne.size())+1; 
     arrListTwo.add(arrListOne.get(randNum)); 
     arrListOne.remove(arrListOne.get(randNum)); 
     } 
     return arrListTwo; 
    } 

    public String toString() 
    { 
     String output = "The Randomized ArrayList is"; 
     output+=arrListTwo; 
     return output; 
    } 
} 

public class Sequence 
{ 
    public static void main(String [] args) 
    { 
    seq seqObj = new seq(); 
    seqObj.getFilledArr(); 
    seqObj.randNewArr(); 
    System.out.println(seqObj.toString()); 
    } 

} 

Answer 1

вопрос просто говорит это:

сделать массив с номерами 1-10 (не должен быть произвольно заказан). Затем генерирует случайное число между 1-10 и выбирает номер и удаляет этот индекс из массива, который вы создали ранее.

Грубая реализация будет:

ArrayList nums = new ArrayList<Integer>(); // The arraylist with numbers from 1-10 
for(int i = 1; i < 11; i++;) 
    nums.add(i); 

Random r = new Random(); 
int x = r.nextInt(10); 

int[] finalNums = new int[2]; 
finalNums[0] = nums.get(x); 
nums.remove(x); // Remove the number at this index so it won;t be picked up again 

x = r.nextInt(9); // Since we removed one index from arraylist, so total elements are now nine instead of 10. 
finalNums[1] = nums.get(x); 
nums.remove(x); 

Так в чем разница? В этом подходе вы уверены, что он не будет выбирать одинаковый номер дважды. Зачем? Потому что вы удаляете номер, как только вы его выбираете, чтобы он не менялся снова.

EDIT:

Что касается вашей попытки с ArrayList, где вы спросили, что вы пишете в main блоке, вы просто должны вызвать два метода, которые вы создали в своем классе в порядке. Это может быть либо в основном блоке:

public class Sequence 
{ 
    // You need one main method atleast to run the code 
    public static void main(String[] args){ 
     seq seqObj = new seq(); 
     System.out.println(seq.getRandomArray()); 
    } 
} 

Или вы могли бы также назвать эти методы в seq класса конструктор:

public seq() 
{ 
    randNum = new Random(); 
    arr = new int[10]; 
    filledArr = new int[10]; 
    this.getFilledArr(); 
    this.randNewArr(); 
} 

Еще одна вещь, чтобы отметить, что ваш метод для отображения вывода ArrayList является не в порядке. Небольшое уточнение к коду:

import java.util.Random; 
import java.util.ArrayList; 
class seq 
{ 
    private ArrayList<Integer> arrListOne; 
    private ArrayList<Integer> arrListTwo; 
    private Random num; 

    public seq() 
    { 
     num = new Random(); 
     arrListOne = new ArrayList<Integer>(); 
     arrListTwo = new ArrayList<Integer>(); 
     getFillerArr(); 
     randNewArr(); 
    } 

    // You dont have to return ArrayList here 
    public void getFilledArr() 
    { 
     for(int i = 1; i < 11 ; i++) 
     { 
      arrListOne.add(i); 
     } 
    } 

    // You dont have to return ArrayList here 
    public void randNewArr() 
    { 
     for(int i = 0 ; i < 10 ; i++) 
     { 
      int randNum = num.nextInt(arrListOne.size())+1; 
      arrListTwo.add(arrListOne.get(randNum)); 
      arrListOne.remove(arrListOne.get(randNum)); 
     } 
    } 

    // A method that returns you random array list so you can easily use it following rules of encapsulation 
    public ArrayList<Integer> getRandomArray() { 
     return this.arrListTwo; 
    } 
} 

public class Sequence 
{ 
    public static void main(String[] args){ 
     seq seqObj = new seq(); 
     System.out.println(seq.getRandomArray()); 
    } 
} 

EDIT # 2:

Для вашей проблемы negative bound exception, Это как ваш код должен быть:

public seq() 
    { 
     num = new Random(); 

     // Do not try to specify size of Array List here. THey don't have fixed size. 
     arrListOne = new ArrayList<Integer>(); 
     arrListTwo = new ArrayList<Integer>(); 
     getFillerArr(); 
     randNewArr(); 
    } 

    public void getFilledArr() 
    { 
     // Manually iterate for 10 elements. 
     for(int i = 1; i < 11 ; i++) 
     { 
      arrListOne.add(i); 
     } 
    } 

    public ArrayList randNewArr() 
    { 
     for(int i = 0 ; i < 10 ; i++) 
     { 
     // Do not add +1 here, actual array size is already 1 less than the size you get from #size() method. 
     int randNum = num.nextInt(arrListOne.size()); 
     arrListTwo.add(arrListOne.get(randNum)); 
     arrListOne.remove(arrListOne.get(randNum)); 
     } 
     return arrListTwo; 
    } 

Объяснение:

arrListOne = new ArrayList<Integer>(10); 

Здесь вы пытаетесь создать список массивов фиксированного размера 10? Но ArrayLists не имеют фиксированного размера. Так что это не сработает. Следовательно, ваша петля тоже не работает:

public ArrayList getFilledArr() 
{ 
    for(int i = 1; i < arrListOne.size()+1 ; i++) 
    { 
     arrListOne.add(i); 
    } 
    return arrListOne; 
} 

(массив имеет 0 размер, поэтому цикл не запускается).

Следовательно, вы получаете это исключение при получении случайного числа.

PS: Плохо, прошло некоторое время с тех пор, как я сделал java. Как-то я пропустил это, читая этот код.

Answer 2

Проблема в том, что я должен был бы назвать GETRA ndNum() 10 раз, чтобы получить 10 разных номеров, а затем называть fillArr, чтобы поместить его внутрь. Это ALOT ввода. Есть ли способ лучше?

Да, это так.

Используйте это:

public int [] filledArr() 
{ 
    for (int i = 0 ; i < arr.length; i++) 
    { 
     arr[i] = randNum.nextInt(10)+1; 
    } 

return arr; 
} 

так вы кодирования меньше и результат будет тот же.

Answer 3

Подсказка: кажется, вы не поняли предложенный «умный» метод; он должен действовать следующим образом:

1. Сформировать массив из 10 целых чисел, не случайно, просто поместите все номера, заказанные от 1 до 10. Кроме того генерировать пустой массив.

2. В цикле выберите случайный элемент из первого массива и переместите его во второй массив.

Можете ли вы продолжить здесь?

---

Edit: основные проблемы, связанные с вашей третьей попытки являются:

В int randNum = num.nextInt(arrListOne.size())+1; вы, кажется запутанным две вещи, значение целого числа, и его положение в массиве. То, что вы хотите выбрать случайным образом в диапазоне (начиная с нуля) является положение, следовательно, вы должны написать вместо int randPos = num.nextInt(arrListOne.size());

Кроме того, структура класса не очень хорошо, вы должны закодировать класс с методом nextPermutation(), все массивы/списки должны жить внутри этого метода, а только state, которые должны храниться как поля внутри класса, должны быть случайным генератором. Я предлагаю, чтобы закодировать все в этой структуре:

public class PermGen { 

    public final int SIZE = 10; 
    private final Random rand = new Random(); 

    /* returns a new permutation of elements from 1 to 10 (size) */ 
    public int[] nextPermutation() { 
     // create the two lists/arrays here 
     int[] res = new int[SIZE]; 
     List<Integer> list1 = new ArrayList<>(); // or LinkedList 
     // ... fill list1 
     for(int i = 0; i < SIZE; i++) { 
      // pick a random pos1 from list, move the element to res 
      // ... 
      res[i] = list1.remove(randpos); // move the element 
     } 
     return res; 
    } 
} 

Answer 4

Просто идея:

import java.util.ArrayList; 
int LEN = 10; 
ArrayList<Integer> oldArray = new ArrayList<Integer>(); 
for (int i = 0; i < LEN; i++) 
    oldArray.add(i+1); 
int[] newArray = new int[LEN]; 
for (int i = 0; i < LEN; i++) { 
    int pos = (int)(Math.random() * oldArray.size()); 
    newArray[i] = oldArray.remove(pos); 
} 

Не уверен, что, если она отвечает критериям (с ArrayList и все, но просто предложение)

Answer 5

Так как это домашняя работа проблема, очевидно, я не хочу давать вам фактический код, а скорее описывать его.   (Так как вы сказали, что это не было, я добавил полный ответ выше, но решил также держать это объяснение.)

В принципе, вы «перетасовка колоды карт.» Начните с инициализации массива последовательным 1..10.

Теперь вы можете «перетасовать» колода проходом по палубе от 1..10, выбора карты-номер случайным образом, что это больше или равно ("на или вперед-оф. .. ") позицию вашего курсора. Swap две карты.

Это функционально эквивалентно «удалению карты случайным образом из другого массива», но она использует тот факт, что эта «куча перетасованных карт» растет точно так же, как «куча сортированных карточек, «Сжимается. Следовательно, все это можно сделать только в одном массиве. Перемешанная часть находится за курсором; (первоначально) часть в порядке находится или вперед.

Только один проход, у вас есть превосходно перетасованная колода карт, которая, как известно, не содержит дубликатов.

Answer 6

Псевдо-код (не Java):

Card deck[], temp; 
int i, j; 

// fill the deck 
for (i = 0; i < 10; i++) deck[i] = i; 

// Shuffle 'em. Runs stern-to-stem because of 'rand()' 
for (i = 9; i > 0; i--) { // no need for (i == 0) ... 
    j = rand(i); // returns value in the inclusive range [0..i] 

    // it's just fine if (i == j) ... although it usually won't be ... 
    temp = deck[i]; // set-aside the card in the cursor-position 
    deck[i] = deck[j]; // replace it with the randomly-chosen card 
    deck[j] = temp;  // then put the original card where it can get picked 
} 

В этой версии прогонов алгоритма, карты за положение курсора i тасуются карты, в то время как карты в [0..i] являются полу-сортированный пул карт, из которых можно произвольно рисовать.(Этот пул начинает отлично отсортирован, но становится несортированным, как элементы получают обменены на него, но кто-заботится.)

Вы увидите, что этот алгоритм, работающий в массиве одного в один проходе, производит тщательно перетасованная колода, которая не содержит дубликатов. Алгоритм идентичен тому, который использует два массива, но гораздо эффективнее:   массив перемещается на место и никогда не изменяется.

Может использоваться любой контейнерный класс (изменяемый по размеру или не ...), но выбранный контейнер должен иметь базовую реализацию, которая позволяет извлекать любой случайно выбранный элемент со сравнимой скоростью независимо от того, где он находится. Например, «связанный список» не был бы эффективным выбором.