來自字符串的不同數字算法

我正在研究一個簡單的遊戲，並且我需要採用諸如「hello world」之類的詞或短語並將其轉換爲一系列數字。來自字符串的不同數字算法

的標準是：

號碼也必須不同
需要配置數的最大序列的能力。 IE 10號碼總數。
需要能夠按順序配置每個數字的最大範圍。
必須是確定性的，也就是說，我們應該每次對同一個輸入詞組獲得相同的序列。

我試着打破這個問題，像這樣：在「世界你好」 = 104 101 108 108 111 32 119 111 114 108 100

刪除everyother號，直到我們滿足總數（10：

字符轉換爲ASCII碼數這種情況下）
FOREACH數如果數>最大數量然後除以2直至數< =最大數
如果任何編號重複增加或減少第一次出現直到滿意。（這可能會導致一個問題，因爲你可以通過解決另一個副本創建一個副本）

有沒有更好的方法來做到這一點，或者我是在正確的軌道上？如上所述，我想我可能會遇到的問題與刪除區別。

來源

2013-02-21 The Muffin Man

是否有任何要求不同的詞/短語產生不同的數字系列？ – 2013-02-21 17:13:01

@TedHopp對不起，我不確定我完全理解你的問題。 – 2013-02-21 17:15:33

「什麼是最好的X算法」似乎比SO更適合PE。 – 2013-02-21 17:15:34

如果你想限制輸出系列的大小 - 那麼這是不可能的。

證明：
假設你的輸出是一系列大小k，每個的範圍爲r <= M一些預定義的M，則有至多k*M可能的輸出。

但是，有無數的輸入，具體有k*M+1不同的輸入。

從pigeonhole principle（其中輸入是鴿子，輸出是鴿子孔） - 在一個鴿子（輸出）中有2個鴿子（輸入） - 因此無法達到要求。

原來的答覆，提供解決方法不限制輸出系列尺寸：

您可以使用質數，讓p1,p2,...是該系列素數的。
然後，使用number[i] = ascii(char[i]) * p_i
每個字符的範圍的字符串轉換成一系列數字顯然是那麼[0,255 * p_i]

由於每個i,j這樣i != j - >p_i * x != p_j * y（每個x,y） - 你的獨特性。然而，這在理論上是非常好的，因爲生成的數字可能會快速增長，並且對於實際實現，您將需要一些大數字庫，例如Java的BigInteger（無法回想C＃等價物）。無系列限制的鬆弛）是：

number[i] = ascii(char[i]) + 256*(i-1)

在這裏用於number[i]範圍是[256*(i-1),256*i)，和元素仍然不同。

來源

2013-02-21 17:14:35 amit

當您的字符串跨越比該系列允許的更多字符時會發生什麼？ – NominSim 2013-02-21 17:17:07

@NominSim好吧，既然有無數的素數，這個系列就是無限的 - 所以這個字符串不能跨越那麼長。然而，對於非常大的字符串，找到下一個素數可能會非常棘手（但這似乎不成問題） – amit 2013-02-21 17:18:25

我指的是OP的暫定「解決方案」，他說'刪除其他數字直到我們滿意總數（在這種情況下爲10）'這似乎表明他希望能夠限制輸出序列而不必限制輸入。 – NominSim 2013-02-21 17:20:39

讓我們儘可能輕鬆地消除您的標準。對於不同的確定性，只需使用哈希碼。（哈希其實是不能保證是不同的，但極有可能是）：

string s = "hello world"; 
uint hash = Convert.ToUInt32(s.GetHashCode());

注意，我轉換的符號int從GetHashCode返回簽名，以避免一的機會「 - 」出現。

然後，對於每個號碼的最大範圍，只需convert the base。

這給您留下最大的順序標準。不理解你的要求更好，我只能建議被截斷如果必要的話：

hash.toString().Substring(0, size)

期截斷留下了機會，你將不再是不同的，但必須建立在可以接受你的要求？正如阿米特在另一個答案中解釋的那樣，你不能有無限的輸入和無限的輸出。

來源

2013-02-21 17:30:48

僅僅指出「極有可能」是不同的，因爲散列碼只有2^32種可能性。 – NominSim 2013-02-21 17:54:55

數學上，它是理論上可以做你想做的，但你不能做到這一點在C＃：

如果你的輸出要求是不同的，那麼你就不能任何信息編碼後丟失該字符串使用ASCII值。這意味着如果您將輸出大小限制爲n數字，則數字必須包含來自編碼的所有信息。

因此，對於你的例子

的「Hello World」 - > 104 101 108 108 111 32 119 111 114 108 100

你就必須保持每個這些數字的含義。最簡單的方法就是將數字填充到三位數字並將它們連接在一起成爲一個大數字......使最大數字爲1時的結果爲104101108111032119111114108100 （您可以看到問題變爲何處，對於任意長度的輸入你需要非常大的數字。）所以當然可以編碼任意長度的字符串輸入到n數字，但數字會變得非常大。

如果用數字表示數字，那麼不能有不同的輸出，正如@amit在pidgeonhole原理中的解釋。

來源

2013-02-21 17:36:42 NominSim

請注意，這會使其他放寬忽略「需要按順序爲每個數字配置最大範圍的能力」。但是，正如我們已經確定的那樣 - 至少有一次放鬆無法完成。 – amit 2013-02-21 17:40:59

除非我們可以使用實數，然後只是將數字轉換爲實數（併爲結尾添加明顯的區別）。在這種情況下，由於我們在範圍[0,1]中有無限實數，所以我們可以使用這個範圍來表示所有字符串。 – amit 2013-02-21 17:45:14

@amit謝謝，你是對的...我也喜歡你的解決方法... 0與尾數無限序列的數字當然仍然在範圍[0,1] :) – NominSim 2013-02-21 17:48:34

好的，所以在一個評論中，你說過這只是選擇彩票號碼。在這種情況下，你可以做這樣的事情：

public static List<int> GenNumbers(String input, int count, int maxNum) 
{ 
    List<int> ret = new List<int>(); 
    Random r = new Random(input.GetHashCode()); 
    for (int i = 0; i < count; ++i) 
    { 
     int next = r.Next(maxNum - i); 
     foreach (int picked in ret.OrderBy(x => x)) 
     { 
      if (picked <= next) 
       ++next; 
      else 
       break; 
     } 
     ret.Add(next); 
    } 
    return ret; 
}

的想法是種子隨機數發生器字符串的哈希碼。其餘的只是選擇數字而沒有更換。我相信它可以更有效地寫入 - 另一種方法是生成所有maxNum數字並隨機洗牌第一個count。警告，未經測試。

我知道.Net運行時的新版本使用隨機的String哈希碼算法（所以運行結果會有所不同），但我相信這是選擇加入。編寫自己的哈希算法是一個選項。

來源

2013-02-22 20:50:39 bmm6o

但是這將返回同樣的結果反覆輸入相同的輸入？ – 2013-02-22 22:55:01

是的。 PRNG的輸出是其種子的確定性結果。 – bmm6o 2013-02-23 18:56:36

來自字符串的不同數字算法

回答

相關問題