rust - How to map an integer in a specific range to the same range randomly and uniquely? - Stack Overflow

admin管理员组

文章数量:1277344

I want to generate a unique and random code which looks like AAA-nnn from a sequence number:

seq	code (unique and random)
0	DFZ-980
1	FGG-443
2	CCZ-189
...	...

I want to generate a unique and random code which looks like AAA-nnn from a sequence number:

seq	code (unique and random)
0	DFZ-980
1	FGG-443
2	CCZ-189
...	...

A ranges from 'A' to 'Z', n ranges from '0' to '9', so there are 26^3 * 10^3 = 17,576,000 possible combinations.

So this question converts to a unique random mapping from [0, 17576000) to [0, 17576000).

I found some related questions and answers suggesting shifting, addition, multiplication and bit operations, but they all seem to extend the range, or fix the range in 2's power like 2^64 or 2^256. I have no idea how to keep the output in a much smaller range while not breaking the uniqueness. Some other posts point me to PRP (pseudo-random permutation), which looks promising, but I know nothing about cryptography, and failed to find an implementation of it (wikipedia says AES-128 and DES implement PRP, but the range seems to be constrained to 2^64, 2^56 and 2^128 ?).

Security is not necessary, this is just part of a game, which assigns 'fancy' (but unique) codes to some objects which will be displayed to players.

• rust
• mapping

Share Improve this question Follow asked Feb 24 at 6:29 LittleSayaLittleSaya 30811 gold badge33 silver badges1010 bronze badges

Add a comment  | 

1 Answer 1

Sorted by: Reset to default 2

Since the code space are 26 * 26 * 26 * 10 * 10 * 10, you can find any integer that is coprime with 17576000, and keep wrapped adding to it to reach all the number.

To use a smaller example let's say code are 0-9, there are 10 total code, we can pick 3 as the step and keep wrapping:

0 -> 3 -> 6 -> 9 -> 2 -> 5 -> 8 -> 1 -> 4 -> 7 -> 0 (again)

it cycled all number without repeating.

for the code, you can pick the step size 1 to iterate sequentially, or a big number the coprime with 17576000

Example

use std::collections::BTreeSet;

fn main() {
    // 26 * 26 * 26 * 10 * 10 * 10
    // 2^3 * 13^3 * 2^3 * 5^3
    // 2^6 * 5^3 * 13^3
    let mut k: u32 = 0;
    
    // any things that is not multiple of 2, 5, and 13
    let step: u32 = 
        // 1; // iter all code in order.
        // 2_u32.pow(10) - 1; // the step is close, result in less random jump
        2_u32.pow(4) * 5_u32.pow(2) * 3 * 7 * 17* 23 * 31 - 1; // very random jump
        // 2_u32.pow(15) - 1;

    let n: u32 = 26 * 26 * 26 * 10 * 10 * 10;

    let mut set = BTreeSet::new();

    // for i in 0..n {
    for i in 0..10000 {
        let code = k_to_code(k);
        println!("{}",code);
        // make sure it is not already generatead
        assert!(set.insert(code));
        k = (k + step) % n;
    }
}

fn k_to_code(mut k: u32) -> String {
    // you can swap around the order of quotient to make more random result
    let a = k % 10;
    k /= 10;
    let b = k % 10;
    k /= 10;
    let c = k % 10;
    k /= 10;
    let x = k % 26;
    k /= 26;
    let y = k % 26;
    k /= 26;
    let z = k % 26;

    let x = (x as u8 + 65) as char;
    let y = (y as u8 + 65) as char;
    let z = (z as u8 + 65) as char;

    format!("{}{}{}-{}{}{}", z, y, x, c, b, a)
}

本文标签： rustHow to map an integer in a specific range to the same range randomly and uniquelyStack Overflow