Math

康托爾對角線論證？我們真的能找到那條「獨特」的字串嗎？🤯

Martin

21 Feb 2025 • 3 min read

引言

想找出一堆字串入面的唯一字串？我天真地使用遞迴去暴力尋找，結果：蛤？怎麼時間複雜度比其他使用者高;_;

結果我發現還有更好的解決方法！那就是康托爾對角線論證。讓我們探討他的威力吧！

對日常生活及編程也沒有幫助。只是一個冷知識！如果你為了編程比賽，你可以看下去。

對角線論證是什麼?

它是一個在現實很難運用到的東西啦！！！來，我們玩一個遊戲！
你有沒辦法在不使用任何搜尋工具的情況下，找出沒有在下面的數組？這時候，對角線論證就能用上了。

１０１１０１００００１０１０１０１０１０１０１０１０１０１０
０１０１００１００００１０１０１００１０１０１０１００１０１
１０１０１００１０００１００１０１０１０１００１０１０１００
０１０１００００１０１００１０１０１０１１０１０１１０１０１
１０１０１００００１１０１０１１０１０１１０１００１０１０１
００００００１０１０１０１００１１１１００１１１１１１０１０
１１０１０１０１０１１１１１０１１１０１１１１１１１１１０１
１０１０１１０１１１０１１０１１１０１１１１１１０１１１１０
１０１０１１００１１１１０１１１０１１１１０１００１０１１０
１１１１０１１１１１１１００００００００１００００１０００１
１００００１００００１００１０００００１１１１１１０００００
１１１１１１００００１１１１００００１０１１１０１１０１０１
１０１０１１０１１０１０１０１００１００１０１００１０１０１
１０１００１００１０１０１１１０１０００１０００１１１１１１
１０１０１１０１００１１１００１００００１１０１０１０１０１
１０１０１１０１００１１１００１００１０１０１０００１１１１
１０１０１１０１００１１１００１００００１１０１０１１１１０
１０１０１１００１０１０１０００００００１１０１０１１１０１
１１１０１１１０１１１０１１１１１１１１１１０１０１１１０１
１１１１００１１１１１１１１００１１１１１１１１００１１１１
１０１１１１０１００１０１１０１０１１１１０１００１０１１０
００１００１０１００１０１０１００１００１０１００１０１０１
１０１１１０１１０１１１０１１１１１１０１１１１０１１０１０
１００１０１０１１１０１０００１０００１１１１１１１１０１０
１００１０１０１０００００００１００１０１０１０００００００
１０１０１１００１１１１０１１１０１１１１０１００１０１１１
１０１０１１００１１１１０１１１０１１１１０１００１０１０１
１１１１００１１１１１１１１００１１１１１１１１００１１０１
１１１１００１１０１１１１１００１１１１１１１１００１１０１
１１１１００１１１１１１１１１０１１１１１１１１００１１０１

解法（我將對角線附近改為＊為方便查閱）

１＊１１０１００００１０１０１０１０１０１０１０１０１０１０
＊１＊１００１００００１０１０１００１０１０１０１００１０１
１＊１＊１００１０００１００１０１０１０１００１０１０１００
０１＊１＊０００１０１００１０１０１０１１０１０１１０１０１
１０１＊１＊０００１１０１０１１０１０１１０１００１０１０１
００００＊０＊０１０１０１００１１１１００１１１１１１０１０
１１０１０＊０＊０１１１１１０１１１０１１１１１１１１１０１
１０１０１１＊１＊１０１１０１１１０１１１１１１０１１１１０
１０１０１１０＊１＊１１０１１１０１１１１０１００１０１１０
１１１１０１１１＊１＊１００００００００１００００１０００１
１００００１０００＊１＊０１０００００１１１１１１０００００
１１１１１１００００＊１＊１００００１０１１１０１１０１０１
１０１０１１０１１０１＊１＊１００１００１０１００１０１０１
１０１００１００１０１０＊１＊０１０００１０００１１１１１１
０１１１１００１１１１１１＊０＊００１１１０１１０１０１１０
１０１０１１０１００１１１０＊１＊０１０１０１０００１１１１
１０１０１１０１００１１１００＊０＊００１１０１０１１１１０
１０１０１１００１０１０１０００＊０＊０１１０１０１１１０１
１１１０１１１０１１１０１１１１１＊１＊１１０１０１１１０１
１１１１００１１１１１１１１００１１＊１＊１１１００１１１１
１０１１１１０１００１０１１０１０１１＊１＊１００１０１１０
００１００１０１００１０１０１００１００＊０＊００１０１０１
１０１１１０１１０１１１０１１１１１１０１＊１＊０１１０１０
１００１０１０１１１０１０００１０００１１１＊１＊１１０１０
１００１０１０１０００００００１００１０１０１＊０＊００００
１０１０１１００１１１１０１１１０１１１１０１０＊１＊１１１
１０１０１１００１１１１０１１１０１１１１０１００＊０＊０１
１１１１１００１１１１１１１０１００１１１０１１０１＊１＊１
１１１１１００１１１１１１１０１００１１１０１１０１０＊１＊
１１１１１００１１１１１１１０１００１１１０１１０１０１＊１

💡 對角線方法的關鍵步驟
1️⃣ 提取對角線上的數字（即第 i 行的第 i 個位元）
１１１１１００１１１１１１１０１００１１１０１１０１０１１１
2️⃣ 翻轉每個位元（0 → 1，1 → 0）
０００００１１０００００００１０１１０００１００１０１０００
3️⃣ 新產生的二進制字串，必然與原列表中的每一行都不同！
👉 這就是為什麼我們總能找到一個「不在列表中的獨特數組」！😎

為何一定要轉換？

如果你有注意，對角線其實有與上面30組裡面其中1組是相同。這就是為何一定要轉換，原理其實在每組數字裡選擇1個數字來轉換。這亦就做成這個原理的缺陷，必須附合以下條件才能使用。
數組數量\(\le\)數組長度

為何我使用極端的例子？

因為在CodeForce或Leetcode裡，往往也有很極端的找唯一字串的題目。這樣可以令你對對角線論證更深的記憶。>ｗ＜

結語

我學了一個集合論的東西啊ＯＡＯ！！　但只對編程比賽有幫助，就沒任何作為了！！　康托爾！！給我從棺材裡出來！ＱＡＱ

Cantor's Diagonal Argument: Can We Really Find That "Unique" String? 🤯🍺

Introduction

Trying to find a unique string among a bunch of binary strings?
I naively used brute force to search, and the result was: huh? 🤨 Why is my time complexity higher than everyone else's? ;_;

Then, I discovered a better solution! That is Cantor's Diagonal Argument. Let's explore its power! 🚀

In daily life and coding, this theory is useless. It's just an interesting piece of knowledge! But if you're into competitive programming, you might want to keep reading.

What is the Diagonal Argument?

This is something that's very difficult to apply in real life!!! But hey, let's play a game! 🎮
Can you, without using any search tools, find a number that is not in the list below? 🤔
Try using the diagonal method and see if you can figure it out yourself!

Solution (I've marked the diagonal elements with * for easy reference)

💡 Key Steps in the Diagonal Method

1️⃣ Extract the diagonal elements (i.e., the i-th bit from the i-th row).
１１１１１００１１１１１１１０１００１１１０１１０１０１１１
2️⃣ Flip each bit (0 → 1, 1 → 0).
０００００１１０００００００１０１１０００１００１０１０００
3️⃣ The new binary string must be different from every row in the original list!
And that's why we can always find a unique number that isn't in the list! 😎

Why Do We Need to Flip the Bits?

If you look carefully, you’ll notice that one of the diagonal sequences already exists in the list. This is why we must flip the bits—otherwise, we might accidentally end up with a duplicate. For this method to work, the number of sequences must be ≤ the length of each sequence.

Why Did I Use an Extreme Example?

Because in Codeforces or LeetCode, there are often very extreme problems where you need to find the only unique binary string.This method ensures you'll never forget Cantor's Diagonal Argument! >w<

Conclusion

I learned a concept from set theory OAO!! But except for being useful in competitive programming, it has no practical use at all!! Cantor!! Get out of your grave and explain this to me! QAQ