Tạo một cách xác định một mảng các chỉ mục dựa trên số đầu vào

Vui lòng xem phần Tham khảo bên dưới để biết các điều khoản.

Có phương pháp một chiều đã biết để tạo ra một mảng các chỉ mục, chỉ dựa trên hai phần tử đầu vào:

• chiều dài của mảng kết quả
• số, được sử dụng làm khóa để tạo mảng một cách xác định

Nếu chỉ tồn tại một phương thức chỉ có thể tạo ra các mảng có độ dài cố định - thì đó cũng có thể là một khởi đầu tốt cho tôi.

Ví dụ:

Thẩm quyền giải quyết:

• một mảng chỉ số:
  Mảng, có giá trị là tất cả các số nguyên từ 0 đến (độ dài của mảng - 1), không có thứ tự.
• xác định chức năng:
  Một chức năng, tạo ra cùng một kết quả mỗi khi cung cấp cùng một dữ liệu đầu vào

Bắt đầu với một mảng các chỉ số được sắp xếp.

Các Xáo trộn Durstenfeld hoạt động bằng cách tiếp tục duyệt qua mảng, coi một phần của mảng là đã xáo trộn và phần còn lại của mảng là chưa xáo trộn. Nó chỉ đơn giản hoán đổi từng mục trong mảng với một mục ngẫu nhiên từ vùng chưa xáo trộn cho đến khi mảng được xáo trộn hoàn toàn.

Tất cả các hoán vị sẽ được trang bị.

Một CSPRNG xác định (được nhập bằng số đầu vào của bạn) được sử dụng để tạo các chỉ số ngẫu nhiên được chọn trong quá trình xáo trộn.

const csprng = new csprng(<hạt giống số đầu vào>);
const len ​​= 10;
const a = Mảng mới(len);
for(let i=0; i<len; i++) a[i] = i;

for(let i=0; i<len; i++) {
  hãy hoán đổi Index = nextDeterministicallyRandomIntBetween(i, len, csprng);
  để tmp = a[i]; a[i] = a[chỉ số hoán đổi]; a[chỉ số hoán đổi] = tmp; // tráo đổi
}

hàm nextDeterministicallyRandomIntBetween(lowerBoundInclusive, 
    upperBoundExclusive, csprng) {

  trả lại LowerBoundInclusive +
    nextDeterministicallyRandomIntLowerThan(upperBoundExclusive-lowerBoundInclusive, csprng);
}

hàm nextDeterministicallyRandomIntLowerThan(upperBoundExclusive, csprng) {
  // xác định số bit "b" tối thiểu cần thiết để biểu diễn
  // (upperBoundExclusive-1). Sau đó liên tục yêu cầu csprng cho b bit
  // cho đến khi nó trả về kết quả thấp hơn upperBoundExclusive
  hãy để b = Math.ceil(Math.log(upperBoundExclusive) / Math.log(2));
  để r;
  làm {
    r = csprng.nextBits(b);
  } while (r>=upperBoundExclusive);
  trả lại r;
}