Memetakan dua bilangan bulat menjadi satu, dengan cara yang unik dan deterministik

Bayangkan dua bilangan bulat positif A dan B. Saya ingin menggabungkan keduanya menjadi satu bilangan bulat C.

Tidak mungkin ada bilangan bulat D dan E lainnya yang digabungkan ke C. Jadi menggabungkannya dengan operator tambahan tidak berfungsi. Umpamanya 30 + 10 = 40 = 40 + 0 = 39 + 1 Tidak juga concatination bekerja. Misalnya "31" + "2" = 312 = "3" + "12"

Operasi kombinasi ini juga harus deterministik (selalu menghasilkan hasil yang sama dengan input yang sama) dan harus selalu menghasilkan bilangan bulat baik di sisi positif atau negatif dari bilangan bulat.

Anda sedang mencari NxN -> Npemetaan bijektif . Ini digunakan untuk misalnya pas . Lihatlah PDF ini untuk pengantar apa yang disebut fungsi pasangan . Wikipedia memperkenalkan fungsi pemasangan khusus, yaitu fungsi pemasangan Cantor :

Tiga komentar:

• Seperti yang orang lain jelaskan, jika Anda berencana untuk mengimplementasikan fungsi pairing, Anda mungkin segera menemukan bahwa Anda membutuhkan bilangan bulat besar yang sewenang-wenang (bignum).
• Jika Anda tidak ingin membuat perbedaan antara pasangan (a, b) dan (b, a), maka urutkan a dan b sebelum menerapkan fungsi pemasangan.
• Sebenarnya saya berbohong. Anda mencari ZxZ -> Npemetaan bijektif . Fungsi Cantor hanya bekerja pada angka non-negatif. Namun ini bukan masalah, karena mudah untuk mendefinisikan suatu penambangan f : Z -> N, seperti:
  • f (n) = n * 2 jika n> = 0
  • f (n) = -n * 2 - 1 jika n <0

Fungsi pemasangan pasangan benar-benar salah satu yang lebih baik di luar sana mengingat itu sederhana, cepat dan efisien ruang, tetapi ada sesuatu yang lebih baik diterbitkan di Wolfram oleh Matthew Szudzik, di sini . Batasan fungsi pasangan Cantor (relatif) adalah bahwa kisaran hasil yang disandikan tidak selalu tetap dalam batas-batas 2Ninteger bit jika inputnya adalah Ninteger bit dua . Artinya, jika input saya adalah 16bilangan bulat dua mulai dari 0 to 2^16 -1, maka ada 2^16 * (2^16 -1)kombinasi input yang mungkin, sehingga dengan angka bit Prinsip Pigeonhole yang , kita memerlukan output ukuran setidaknya , yang sama dengan , atau dengan kata lain, peta jelas harus layak idealnya. Ini mungkin tidak terlalu penting praktis dalam dunia pemrograman.2^16 * (2^16 -1)2^32 - 2^1632

Fungsi pemasangan penyanyi :

(a + b) * (a + b + 1) / 2 + a; where a, b >= 0

Pemetaan untuk dua bilangan bulat maksimal 16 bit (65535, 65535) maksimum adalah 8589803520 yang seperti yang Anda lihat tidak dapat masuk ke dalam 32 bit.

Masukkan fungsi Szudzik :

a >= b ? a * a + a + b : a + b * b;  where a, b >= 0

Pemetaan untuk (65535, 65535) sekarang akan menjadi 4294967295 yang seperti yang Anda lihat adalah bilangan bulat 32 bit (0 hingga 2 ^ 32 -1). Di sinilah solusi ini ideal, hanya memanfaatkan setiap titik di ruang itu, jadi tidak ada yang bisa mendapatkan ruang lebih efisien.

Sekarang mempertimbangkan fakta bahwa kita biasanya berurusan dengan implementasi yang ditandatangani dari sejumlah ukuran dalam bahasa / kerangka kerja, mari kita pertimbangkan signed 16bilangan bulat mulai dari -(2^15) to 2^15 -1(nanti kita akan melihat bagaimana memperluas bahkan ouput untuk menjangkau rentang yang ditandatangani). Karena adan bharus positif, mereka berkisar dari 0 to 2^15 - 1.

Fungsi pemasangan penyanyi :

Pemetaan untuk dua bilangan bulat paling banyak ditandatangani 16 bit (32767, 32767) akan menjadi 2147418112 yang hanya sedikit dari nilai maksimum untuk bilangan bulat 32 bit yang ditandatangani.

Sekarang fungsi Szudzik :

(32767, 32767) => 1073741823, jauh lebih kecil ..

Mari memperhitungkan bilangan bulat negatif. Itu di luar pertanyaan awal yang saya tahu, tetapi hanya menguraikan untuk membantu pengunjung masa depan.

Fungsi pemasangan penyanyi :

A = a >= 0 ? 2 * a : -2 * a - 1;
B = b >= 0 ? 2 * b : -2 * b - 1;
(A + B) * (A + B + 1) / 2 + A;

(-32768, -32768) => 8589803520 yang merupakan Int64. Output 64 bit untuk input 16 bit mungkin sangat tidak dapat diampuni !!

Fungsi Szudzik :

A = a >= 0 ? 2 * a : -2 * a - 1;
B = b >= 0 ? 2 * b : -2 * b - 1;
A >= B ? A * A + A + B : A + B * B;

(-32768, -32768) => 4294967295 yaitu 32 bit untuk rentang yang tidak ditandatangani atau 64 bit untuk rentang yang ditandatangani, tetapi masih lebih baik.

Sekarang semua ini sementara output selalu positif. Di dunia yang ditandatangani, akan lebih menghemat ruang jika kita bisa mentransfer setengah output ke sumbu negatif . Anda bisa melakukannya seperti ini untuk Szudzik:

A = a >= 0 ? 2 * a : -2 * a - 1;
B = b >= 0 ? 2 * b : -2 * b - 1;
C = (A >= B ? A * A + A + B : A + B * B) / 2;
a < 0 && b < 0 || a >= 0 && b >= 0 ? C : -C - 1;

(-32768, 32767) => -2147483648

(32767, -32768) => -2147450880

(0, 0) => 0 

(32767, 32767) => 2147418112

(-32768, -32768) => 2147483647

Apa yang saya lakukan: Setelah menerapkan bobot 2pada input dan melalui fungsi, saya kemudian membagi ouput dengan dua dan mengambil beberapa dari mereka ke sumbu negatif dengan mengalikan dengan -1.

Lihat hasilnya, untuk input apa pun dalam kisaran 16nomor bit yang ditandatangani , outputnya berada dalam batas 32integer bit yang ditandatangani yang keren. Saya tidak yakin bagaimana cara yang sama untuk fungsi pemasangan Cantor tetapi tidak mencoba sebanyak tidak efisien. Selain itu, lebih banyak perhitungan yang terlibat dalam fungsi pemasangan Cantor berarti lebih lambat .

Berikut ini adalah implementasi C #.

public static long PerfectlyHashThem(int a, int b)
{
    var A = (ulong)(a >= 0 ? 2 * (long)a : -2 * (long)a - 1);
    var B = (ulong)(b >= 0 ? 2 * (long)b : -2 * (long)b - 1);
    var C = (long)((A >= B ? A * A + A + B : A + B * B) / 2);
    return a < 0 && b < 0 || a >= 0 && b >= 0 ? C : -C - 1;
}

public static int PerfectlyHashThem(short a, short b)
{
    var A = (uint)(a >= 0 ? 2 * a : -2 * a - 1);
    var B = (uint)(b >= 0 ? 2 * b : -2 * b - 1);
    var C = (int)((A >= B ? A * A + A + B : A + B * B) / 2);
    return a < 0 && b < 0 || a >= 0 && b >= 0 ? C : -C - 1;
}

Karena perhitungan menengah dapat melebihi batas 2Ninteger yang ditandatangani, saya telah menggunakan 4Ntipe integer (pembagian terakhir dengan 2mengembalikan hasilnya ke 2N).

Tautan yang saya berikan pada solusi alternatif menggambarkan grafik fungsi yang memanfaatkan setiap titik di ruang angkasa. Sungguh menakjubkan melihat bahwa Anda dapat secara unik menyandikan sepasang koordinat ke angka tunggal secara terbalik! Dunia angka yang ajaib !!

Jika A dan B dapat diekspresikan dengan 2 byte, Anda dapat menggabungkannya dalam 4 byte. Letakkan A di bagian paling signifikan dan B di bagian paling tidak signifikan.

Dalam bahasa C ini memberi (dengan asumsi sizeof (pendek) = 2 dan sizeof (int) = 4):

int combine(short A, short B)
{
    return A<<16 | B;
}

short getA(int C)
{
    return C>>16;
}

short getB(int C)
{
    return C & 0xFFFF;
}

Apakah ini mungkin?
Anda menggabungkan dua bilangan bulat. Keduanya memiliki kisaran -2,147.483.648 hingga 2.147.483.647 tetapi Anda hanya akan mengambil yang positif. Itu membuat 2147483647 ^ 2 = 4,61169E + 18 kombinasi. Karena setiap kombinasi harus unik DAN menghasilkan bilangan bulat, Anda akan memerlukan semacam bilangan bulat ajaib yang dapat berisi jumlah angka ini.

Atau apakah logika saya cacat?

Cara matematika standar untuk bilangan bulat positif adalah dengan menggunakan keunikan faktorisasi prima.

f( x, y ) -> 2^x * 3^y

The downside adalah bahwa gambar cenderung menjangkau rentang bilangan bulat yang cukup besar sehingga ketika datang untuk mengekspresikan pemetaan dalam algoritma komputer Anda mungkin memiliki masalah dengan memilih jenis yang sesuai untuk hasilnya.

Anda dapat memodifikasi ini untuk menangani negatif xdan ydengan meng-encode sebuah flag dengan kekuatan 5 dan 7 syarat.

misalnya

f( x, y ) -> 2^|x| * 3^|y| * 5^(x<0) * 7^(y<0)

Biarkan angka amenjadi yang pertama, byang kedua. Membiarkan pmenjadi a+1bilangan prima -th, qmenjadi b+1bilangan prima -th

Kemudian, hasilnya adalah pq, jika a<b,atau 2pqjika a>b. Jika a=b, biarkan saja p^2.

Tidak sulit untuk membuat pemetaan:

   1 2 3 4 5 gunakan pemetaan ini jika (a, b)! = (B, a)
1 0 1 3 6 10
2 2 4 7 11 16
3 5 8 12 17 23
4 9 13 18 24 31
5 14 19 25 32 40

   1 2 3 4 5 gunakan pemetaan ini jika (a, b) == (b, a) (mirror)
1 0 1 2 4 6
2 1 3 5 7 10
3 2 5 8 11 14
4 4 8 11 15 19
5 6 10 14 19 24


    0 1 -1 2 -2 gunakan ini jika Anda perlu negatif / positif
 0 0 1 2 4 6
 1 1 3 5 7 10
-1 2 5 8 11 14
 2 4 8 11 15 19
-2 6 10 14 19 24

Mencari tahu bagaimana mendapatkan nilai untuk a sewenang-wenang, b sedikit lebih sulit.

f(a, b) = s(a+b) + adimana s(n) = n*(n+1)/2

• Ini adalah fungsi - itu deterministik.
• Ini juga injeksi - f memetakan nilai yang berbeda untuk pasangan (a, b) yang berbeda. Anda dapat membuktikan ini menggunakan fakta: s(a+b+1)-s(a+b) = a+b+1 < a.
• Ini mengembalikan nilai yang cukup kecil - bagus jika Anda akan menggunakannya untuk pengindeksan array, karena array tidak harus besar.
• Ramah-cache - jika dua (a, b) pasangan dekat satu sama lain, maka f memetakan nomor-nomor yang dekat satu sama lain (dibandingkan dengan metode lain).

Saya tidak mengerti apa yang Anda maksud dengan:

harus selalu menghasilkan bilangan bulat baik di sisi positif atau negatif dari bilangan bulat

Bagaimana saya bisa menulis (lebih besar dari), (kurang dari) karakter di forum ini?

Meskipun jawaban Stephan202 adalah satu-satunya yang benar-benar umum, untuk bilangan bulat dalam rentang terbatas Anda dapat melakukan lebih baik. Misalnya, jika rentang Anda adalah 0..10.000, maka Anda dapat melakukan:

#define RANGE_MIN 0
#define RANGE_MAX 10000

unsigned int merge(unsigned int x, unsigned int y)
{
    return (x * (RANGE_MAX - RANGE_MIN + 1)) + y;
}

void split(unsigned int v, unsigned int &x, unsigned int &y)
{
    x = RANGE_MIN + (v / (RANGE_MAX - RANGE_MIN + 1));
    y = RANGE_MIN + (v % (RANGE_MAX - RANGE_MIN + 1));
}

Hasil dapat masuk dalam satu integer untuk rentang hingga akar kuadrat dari kardinalitas tipe integer. Paket ini sedikit lebih efisien daripada metode yang lebih umum Stephan202. Juga lebih mudah untuk memecahkan kode; tidak membutuhkan akar kuadrat, sebagai permulaan :)

Untuk bilangan bulat positif sebagai argumen dan di mana urutan argumen tidak penting:

1. Inilah fungsi pemasangan yang tidak teratur :

   <x, y> = x * y + trunc((|x - y| - 1)^2 / 4) = <y, x>
   

2. Untuk x ≠ y, inilah fungsi pairing unordered yang unik :

   <x, y> = if x < y:
              x * (y - 1) + trunc((y - x - 2)^2 / 4)
            if x > y:
              (x - 1) * y + trunc((x - y - 2)^2 / 4)
          = <y, x>
   

Lihat ini: http://en.wikipedia.org/wiki/Pigeonhole_principle . Jika A, B dan C memiliki tipe yang sama, itu tidak dapat dilakukan. Jika A dan B adalah bilangan bulat 16-bit, dan C adalah 32-bit, maka Anda cukup menggunakan shifting.

Sifat utama dari algoritma hashing adalah bahwa mereka tidak dapat memberikan hash yang unik untuk setiap input yang berbeda.

Berikut ini adalah ekstensi kode @DoctorJ ke bilangan bulat tak terikat berdasarkan metode yang diberikan oleh @nawfal. Itu dapat menyandikan dan mendekode. Ini bekerja dengan array normal dan array numpy.

#!/usr/bin/env python
from numbers import Integral    

def tuple_to_int(tup):
    """:Return: the unique non-negative integer encoding of a tuple of non-negative integers."""
    if len(tup) == 0:  # normally do if not tup, but doesn't work with np
        raise ValueError('Cannot encode empty tuple')
    if len(tup) == 1:
        x = tup[0]
        if not isinstance(x, Integral):
            raise ValueError('Can only encode integers')
        return x
    elif len(tup) == 2:
        # print("len=2")
        x, y = tuple_to_int(tup[0:1]), tuple_to_int(tup[1:2])  # Just to validate x and y

        X = 2 * x if x >= 0 else -2 * x - 1  # map x to positive integers
        Y = 2 * y if y >= 0 else -2 * y - 1  # map y to positive integers
        Z = (X * X + X + Y) if X >= Y else (X + Y * Y)  # encode

        # Map evens onto positives
        if (x >= 0 and y >= 0):
            return Z // 2
        elif (x < 0 and y >= 0 and X >= Y):
            return Z // 2
        elif (x < 0 and y < 0 and X < Y):
            return Z // 2
        # Map odds onto negative
        else:
            return (-Z - 1) // 2
    else:
        return tuple_to_int((tuple_to_int(tup[:2]),) + tuple(tup[2:]))  # ***speed up tuple(tup[2:])?***


def int_to_tuple(num, size=2):
    """:Return: the unique tuple of length `size` that encodes to `num`."""
    if not isinstance(num, Integral):
        raise ValueError('Can only encode integers (got {})'.format(num))
    if not isinstance(size, Integral) or size < 1:
        raise ValueError('Tuple is the wrong size ({})'.format(size))
    if size == 1:
        return (num,)
    elif size == 2:

        # Mapping onto positive integers
        Z = -2 * num - 1 if num < 0 else 2 * num

        # Reversing Pairing
        s = isqrt(Z)
        if Z - s * s < s:
            X, Y = Z - s * s, s
        else:
            X, Y = s, Z - s * s - s

        # Undoing mappint to positive integers
        x = (X + 1) // -2 if X % 2 else X // 2  # True if X not divisible by 2
        y = (Y + 1) // -2 if Y % 2 else Y // 2  # True if Y not divisible by 2

        return x, y

    else:
        x, y = int_to_tuple(num, 2)
        return int_to_tuple(x, size - 1) + (y,)


def isqrt(n):
    """":Return: the largest integer x for which x * x does not exceed n."""
    # Newton's method, via http://stackoverflow.com/a/15391420
    x = n
    y = (x + 1) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x

Bagaimana dengan sesuatu yang lebih sederhana: Diberikan dua angka, A dan B biarlah rangkumannya: 'A' + ';' + 'B'. Kemudian biarkan output berupa hash (str). Saya tahu bahwa ini bukan jawaban matematis, tetapi skrip python sederhana (yang memiliki fungsi hash bawaan) harus melakukan tugasnya.

Apa yang Anda sarankan tidak mungkin. Anda akan selalu memiliki tabrakan.

Untuk memetakan dua objek ke set tunggal lainnya, set yang dipetakan harus memiliki ukuran minimum dari jumlah kombinasi yang diharapkan:

Dengan asumsi bilangan bulat 32-bit, Anda memiliki 2147483647 bilangan bulat positif. Memilih dua dari ini di mana pesanan tidak menjadi masalah dan dengan pengulangan menghasilkan kombinasi 2305843008139952128. Ini tidak cocok dengan himpunan bilangan bulat 32-bit.

Namun, Anda dapat menyesuaikan pemetaan ini dalam 61 bit. Menggunakan integer 64-bit mungkin paling mudah. Atur kata tinggi ke integer yang lebih kecil dan kata rendah ke yang lebih besar.

Katakanlah Anda memiliki integer 32 bit, mengapa tidak hanya memindahkan A ke 16 bit pertama dan B ke yang lain?

def vec_pack(vec):
    return vec[0] + vec[1] * 65536;


def vec_unpack(number):
    return [number % 65536, number // 65536];

Selain ini sebagai ruang seefisien mungkin dan murah untuk dihitung, efek samping yang sangat keren adalah Anda dapat melakukan matematika vektor pada angka yang dikemas.

a = vec_pack([2,4])
b = vec_pack([1,2])

print(vec_unpack(a+b)) # [3, 6] Vector addition
print(vec_unpack(a-b)) # [1, 2] Vector subtraction
print(vec_unpack(a*2)) # [4, 8] Scalar multiplication

mari kita memiliki dua angka B dan C, yang menyandikannya menjadi satu nomor A

A = B + C * N

dimana

B = A% N = B

C = A / N = C

Diberikan bilangan bulat positif A dan B, misalkan D = jumlah digit yang dimiliki A, dan E = jumlah digit yang dimiliki B Hasilnya dapat berupa gabungan dari D, 0, E, 0, A, dan B.

Contoh: A = 300, B = 12. D = 3, E = 2 hasil = 302030012. Ini mengambil keuntungan dari kenyataan bahwa satu-satunya angka yang dimulai dengan 0, adalah 0,

Pro: Mudah dikodekan, mudah didekodekan, dapat dibaca manusia, angka signifikan dapat dibandingkan terlebih dahulu, potensi untuk dibandingkan tanpa perhitungan, pengecekan kesalahan sederhana.

Cons: Ukuran hasil adalah masalah. Tapi tidak apa-apa, mengapa kita menyimpan bilangan bulat tanpa batas di komputer.

Jika Anda ingin lebih banyak kontrol seperti mengalokasikan bit X untuk angka pertama dan bit Y untuk angka kedua, Anda bisa menggunakan kode ini:

class NumsCombiner
{

    int num_a_bits_size;
    int num_b_bits_size;

    int BitsExtract(int number, int k, int p)
    {
        return (((1 << k) - 1) & (number >> (p - 1)));
    }

public:
    NumsCombiner(int num_a_bits_size, int num_b_bits_size)
    {
        this->num_a_bits_size = num_a_bits_size;
        this->num_b_bits_size = num_b_bits_size;
    }

    int StoreAB(int num_a, int num_b)
    {
        return (num_b << num_a_bits_size) | num_a;
    }

    int GetNumA(int bnum)
    {
        return BitsExtract(bnum, num_a_bits_size, 1);
    }

    int GetNumB(int bnum)
    {
        return BitsExtract(bnum, num_b_bits_size, num_a_bits_size + 1);
    }
};

Saya menggunakan total 32 bit. Idenya di sini adalah bahwa jika Anda ingin misalnya bahwa angka pertama akan hingga 10 bit dan angka kedua akan hingga 12 bit, Anda dapat melakukan ini:

NumsCombiner nums_mapper(10/*bits for first number*/, 12/*bits for second number*/);

Sekarang Anda dapat menyimpan dalam num_ajumlah maksimum 2^10 - 1 = 1023dan num_bnilai maksimum 2^12 - 1 = 4095.

Untuk menetapkan nilai untuk num A dan num B:

int bnum = nums_mapper.StoreAB(10/*value for a*/, 12 /*value from b*/);

Sekarang bnumadalah semua bit (total 32 bit. Anda dapat memodifikasi kode untuk menggunakan 64 bit) Untuk mendapatkan num:

int a = nums_mapper.GetNumA(bnum);

Untuk mendapatkan angka b:

int b = nums_mapper.GetNumB(bnum);

EDIT: bnumdapat disimpan di dalam kelas. Saya tidak melakukannya karena kebutuhan saya sendiri saya membagikan kode dan berharap itu akan membantu.

Terima kasih untuk sumber: https://www.geeksforgeeks.org/extract-k-bits-given-position-number/ untuk fungsi untuk mengekstrak bit dan terima kasih juga untuk mouvicielmenjawab di posting ini. Menggunakan ini untuk sumber saya bisa mencari solusi yang lebih maju