Mã độc đáo kiểu Tinyurl: thuật toán tiềm năng để ngăn ngừa va chạm

Question

Tôi có một hệ thống yêu cầu mã gồm 6 chữ số duy nhất để biểu diễn một đối tượng và tôi đang cố gắng nghĩ ra một thuật toán tốt để tạo ra chúng. Sau đây là các pre-reqs:

• Tôi đang sử dụng một hệ thống cơ sở-20 (không mũ, số nguyên âm, hoặc l để tránh nhầm lẫn và lời nói nghịch ngợm)
  • Các cơ sở-20 cho phép 64 triệu kết hợp
• Tôi sẽ chèn 5-10 nghìn mục cùng một lúc, vì vậy theo lý thuyết tôi sẽ sử dụng chèn hàng loạt, có nghĩa là sử dụng khóa duy nhất có thể sẽ không hiệu quả hoặc đẹp. bắt đầu có nhiều va chạm)
• Nó không nằm ngoài qu estion để lấp đầy 10% kết hợp vì vậy có một tiềm năng lớn cho rất nhiều va chạm
• Tôi muốn chắc chắn các mã đều là phòng không liên tiếp

Tôi đã có một ý tưởng rằng có vẻ như nó sẽ làm việc, nhưng Tôi không đủ giỏi toán để tìm ra cách thực hiện nó: nếu tôi bắt đầu ở 0 và tăng thêm N, sau đó chuyển đổi thành base-20, có vẻ như có một số giá trị cho N cho phép tôi đếm từng giá trị từ 0-63,999,999 trước khi lặp lại bất kỳ.

Ví dụ, đi từ 0 đến 9 sử dụng N = 3 (để 10 mod 3): 0, 3, 6, 9, 2, 5, 8, 1, 4, 7.

Có một số ma thuật toán học phương pháp để tìm ra giá trị của N cho một số lớn hơn số đó có thể đếm qua toàn bộ phạm vi mà không lặp đi lặp lại? Lý tưởng nhất, số tôi chọn sẽ nhảy xung quanh thiết lập sao cho nó không rõ ràng là có một mẫu, nhưng tôi không chắc chắn nó có thể như thế nào.

Ngoài ra, thuật toán băm đảm bảo tính duy nhất cho các giá trị 0-64 triệu sẽ hoạt động, nhưng tôi quá câm để biết nếu có thể.

Answer 1

Tất cả những gì bạn cần là số không chia sẻ yếu tố với không gian chính của bạn. Giá trị dễ nhất là sử dụng số nguyên tố. Bạn có thể google cho số nguyên tố lớn hoặc sử dụng http://primes.utm.edu/lists/small/10000.txt

Answer 2

Toán học của tôi hơi bị gỉ, nhưng tôi nghĩ bạn chỉ cần đảm bảo rằng GCF của N và 64 triệu là 1. Tôi sẽ đi với số nguyên tố không phân chia đồng đều thành 64 triệu) chỉ trong trường hợp.

Answer 3

Bất kỳ số nguyên tố nào không phải là yếu tố của độ dài của chuỗi sẽ có thể kéo dài chuỗi mà không lặp lại. Đối với 64000000, điều đó có nghĩa là bạn không nên sử dụng 2 hoặc 5. Tất nhiên, nếu bạn không muốn chúng được tạo liên tiếp, tạo ra chúng 2 hoặc 5 ngoài có lẽ cũng không phải là rất tốt. Cá nhân tôi thích số 73973!

Answer 4

Đừng phát minh lại bánh xe: http://en.wikipedia.org/wiki/Universally_Unique_Identifier

Answer 5

@Nick Lewis:

Vâng, chỉ khi số nguyên tố không chia 64 triệu. Vì vậy, với mục đích của người hỏi, các con số như 2 hoặc 5 có lẽ sẽ không được khuyến khích.

Answer 6

Có một phương pháp khác để có được kết quả tương tự (nhảy qua toàn bộ giá trị mà không lặp lại, không liên quan), mà không sử dụng số nguyên tố - bằng cách sử dụng maximum length sequences, mà bạn có thể tạo bằng cách sử dụng đăng ký thay đổi được xây dựng đặc biệt.