algorithm – Prompt a function similar to hash, but shorter and without collisions

Question:

It is required to generate from sequential integers, unique non-sequential n-digit codes. Submit hashes, serials, or coupon numbers. An integer id from 0 to K corresponds to exactly one n-digit code. And it is important that sequential codes differ greatly, and not in one or two characters.

Example:

0    KXBR6Z
1    8FLWGG
2    PAZT73

Due to collisions and the brevity of the required codes, popular hash functions are not suitable. No cryptographic strength required. If the villains figure out the algorithm, let them print out all the codes. It is done for beauty. Although, it is also interesting to consider what determines the complexity of guessing the algorithm by X available codes!

Question: tell me the algorithm / function f(i) = s to match between the sets 0..K and n-digit ABC123XYZ . The inverse function would be also interesting: f1(s) = i to get an integer from the code, or to find out that the code is invalid.

Surely, the problem is not new, but I haven't figured out how to look for an answer. Human translation required. )

PS I'm looking for exactly "mathematics", an algorithm, and not a way to hammer unique values ​​into the database, each time I create a new one, checking the uniqueness.

Answer:

Substitution ciphers do this well. The first thing you need to do is expand the alphabet (go from numbers to letters, where several letters will correspond to one number). If it is very important for you to hide the original value, then it makes sense to pre-encrypt the data with block or asymmetric encryption.

threw in an example of code with substitution, the result:

input/encoded/decoded - 123 / efg / 123
input/encoded/decoded - 456 / hij / 456
input/encoded/decoded - 789 / abc / 789
input/encoded/decoded - 012 / def / 012
input/encoded/decoded - 1157232188 / eoiafgpybl / 1157232188

I am at:

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class Substitution {
    private static final int NUMBER_COUNT = 10;
    private static final int LETTER_COUNT = 26;
    private static final int ZERO_ASCII_CODE = 48;
    private static final int A_CHAR_ASCII_CODE = 97;

    // substitution tables
    private static final Map<Character, List<Character>> numToChar = new HashMap<Character, List<Character>>(
            NUMBER_COUNT);
    private static final Map<Character, Character> charToNum = new HashMap<Character, Character>(
            LETTER_COUNT);

    // init tables
    static {
        // add list containers
        for (int i = 0; i < NUMBER_COUNT; i++) {
            numToChar.put(Character.valueOf((char) (ZERO_ASCII_CODE + i)),
                    new LinkedList<Character>());
        }

        // init substitution table
        for (int i = A_CHAR_ASCII_CODE; i < A_CHAR_ASCII_CODE + LETTER_COUNT; i++) {

            // number = (symbol ascii code) mod 9
            Character num = Character
                    .valueOf((char) (i % NUMBER_COUNT + ZERO_ASCII_CODE));
            Character ch = Character.valueOf((char) i);

            numToChar.get(num).add(ch);
            charToNum.put(ch, num);
        }
    }

    public static void main(String[] args) {
        System.out.println("dumping straight substitution table");
        for (Character num : numToChar.keySet()) {
            System.out.println("num to char - " + num + ", replacements = "
                    + numToChar.get(num));
        }
        System.out.println();
        System.out.println("dumping reverse substitution table");
        for (Character ch : charToNum.keySet()) {
            System.out.println("char to num - " + ch + ", replacements = "
                    + charToNum.get(ch));
        }

        // test
        String[] nums = new String[] { "123", "456", "789", "012", "1157232188" };
        String r = null;
        for (int i = 0; i < nums.length; i++) {
            r = decode(nums[i], true);
            System.out.println("input/encoded/decoded - " + nums[i] + " / " + r
                    + " / " + decode(r, false));
        }

    }

    public static String decode(String input, boolean direction) {
        // result buffer
        StringBuilder b = new StringBuilder(input.length());

        // ensure all latters are in lower case
        String data = input.toLowerCase();

        // store indexes (determines which letter to use when coding a number)
        Map<Character, Integer> indexes = new HashMap<Character, Integer>();

        // encode string
        for (int i = 0; i < input.length(); i++) {
            b.append(decode(indexes, data.charAt(i), direction));
        }

        return b.toString();
    }

    // straight - number to letter
    // reverse - letter to number
    private static Character decode(Map<Character, Integer> indexes, char ch,
            boolean direction) {
        // convert character
        Character character = Character.valueOf(ch);
        if (direction) {
            // get list
            List<Character> list = numToChar.get(character);

            // get index to use
            Integer index = indexes.get(character);
            if (null == index) {
                index = Integer.valueOf(0);
            }

            // update index map
            int next = index.intValue() + 1;
            if (next == list.size()) {
                next = 0;
            }

            indexes.put(character, Integer.valueOf(next));

            return list.get(index);
        }

        return charToNum.get(character);
    }
}

This example is strictly "sharpened" for numbers and letters, but, by analogy, you can make a code that will make substitutions of individual characters and / or their sequences

Scroll to Top