Питання Як ефективно партувати шкарпетки з купи?


Вчора я знімав шкарпетки з чистої білизни, і зрозумів, як я робив це, не дуже ефективно. Я виконував наївний пошук - підбираючи один носок і "повторюючи" купу, щоб знайти свою пару. Це вимагає повторення над n / 2 * n / 4 = n2/ 8 шкарпеток в середньому.

Як комп'ютерний вчений я думав, що я міг би зробити? Сортування (відповідно до розміру / кольору / ...) звичайно приходило на думку, щоб досягти рішення O (NlogN).

Хешування або інші рішення, що не використовуються на місці, не є можливістю, оскільки я не можу дублювати свої шкарпетки (хоча це могло б бути добре, якби я міг).

Отже, в основному це питання:

Враховуючи купу Росії n пари шкарпеток, що містять 2n елементи (припустимо, кожен носок має рівно одну пару відповідних), який найкращий спосіб ефективно об'єднати їх з логарифмічним додатковим простором? (Я вважаю, що я пам'ятаю цю кількість інформації, якщо це потрібно).

Я буду вдячний за відповідь, яка стосується наступних аспектів:

  • Генерал теоретичний Рішення для величезної кількості шкарпеток.
  • Фактична кількість шкарпеток не така велика, я не вірю своєму чоловікові / дружині, і у мене більше 30 пар. (І це досить легко відрізнити мої шкарпетки та її, чи може це також використовуватися?)
  • Це еквівалентно елемент відмінності проблеми?

3507
2018-01-19 15:34


походження


Я використовую принцип "голубиної діри", щоб поєднати точно один із стіни праски. У мене 3 різних кольорів шкарпеток (червоний, синій і зелений) та 2 пари кожного кольору. Я забираю по 4 штуки шкарпеток кожен раз, і я завжди складаю пару і працюю. - Srinivas
Ще один принцип дівочої голуби: якщо взяти підмножину n / 2 +1 шкарпетки, там повинно бути принаймні одна пара в цьому підмножині. - wildplasser
Велике питання! Можливо, ви зацікавитеся моєю статтею про пов'язану проблему, яка полягає у обговоренні ймовірності витягування двох збігів шкарпеток з купи: blogs.msdn.com/b/ericlippert/archive/2010/03/22/... - Eric Lippert
Чому не виростає дитина і waitpid так що, як батько, ви навіть не самі сортуєте шкарпетки? - Mxyk
Я вирішив цю проблему, лише володіючи білими шкарпетками з високим коліном. Вони всі збігаються. Я міг просто захопити будь-які два шкарпетки випадковим чином з купи, і вони збігаються. Я ще більше спрощую проблему, не будучи пару шкарпеток. У мене є ящик носок, який я просто кидаю всі мої шкарпетки в непарні. Я випадково вибираю два з ящика щоранку. Я спростив його до O (0). Не може бути простіше, ніж це. :) - Lee


Відповіді:


Запропоновано сортування рішень, але сортування трохи забагато: Нам не потрібно замовлення; нам просто потрібні групи рівності.

Так хешування буде достатньо (і швидше).

  1. Для кожного кольору шкарпеток утворити купу. Ітератуйте всі шкарпетки в кошику для входу і розподілити їх на колірні палі.
  2. Ітератуйте над кожною купою та Розподіліть його іншою метрикою (наприклад, шаблон) у другий набір куп
  3. Рекурсивно застосовують цю схему поки не розподілите всіх шкарпеток дуже маленькі палі, які ви можете візуально обробляти негайно

Цей тип рекурсивного розділення хеш насправді виконується SQL Server коли йому потрібно хеш-приєднання або сукупність хешу над величезними наборами даних. Він розподіляє свій потік вбудованого вхід у багато незалежних розділів. Ця схема лінійно підраховує довільну кількість даних і декілька процесорів.

Вам не потрібне рекурсивне розділення, якщо ви можете знайти ключ розподілу (хеш-ключ), який надає достатньо відра що кожне відро досить мале для обробки дуже швидко. На жаль, я не думаю, що шкарпетки мають таку властивість.

Якщо кожному носію було ціле число, що називається "PairID", то можна було б легко розподілити їх у 10 сегментів відповідно до PairID % 10 (остання цифра).

Найкращий реальний розділ, про який я можу думати, - це створення прямокутник з паль: одне вимірювання - колір, а інший - шаблон. Чому прямокутник? Оскільки нам потрібен O ​​(1) випадковий доступ до палів. (A 3D кубічний також буде працювати, але це не дуже практично.)


Оновлення:

А як на рахунок паралелізм? Чи можуть шви швидше відповідати декільком людям?

  1. Найпростіша стратегія розпаралелювання полягає в тому, щоб декілька працівників брали з кошика введення і поклали шкарпетки на купи. Це лише збільшує масштаби - уявіть, що 100 людей борються за 10 паль. Вартість синхронізації (проявляючи себе як ручне зіткнення та людське спілкування) знищити ефективність і прискорення (див Універсальний закон про масштабованість!) Чи це схильні до тупикові місця? Ні, тому що кожен працівник повинен отримати доступ лише до однієї пачки за один раз. Тільки один "замок" не може бути тупиком. Жилети може бути можливим залежно від того, як люди координують доступ до паль. Вони можуть просто використовувати випадковий відкат подібні мережеві карти роблять це на фізичному рівні, щоб визначити, яка карта може виключно отримувати доступ до мережевого дроту. Якщо це працює НІС, він повинен працювати і для людей.
  2. Це вага майже на невизначений час, якщо кожен робітник має свій набір куп. Тоді працівники можуть взяти великі шматочки шкарпеток із вхідної кошика (дуже мало суперечок, оскільки вони роблять це рідко), і вони не повинні синхронізуватися при розподілі шкарпеток взагалі (оскільки вони мають місцеві набори). Врешті-решт, усім робітникам потрібно об'єднати свої купи. Я вірю, що це може бути зроблено в О (log (робітник count * пали на одного працівника)), якщо працівники складають a дерево агрегації.

А як щодо елемент відмінності проблеми? Як зазначено в статті, проблема розрізнення елемента може бути вирішена в O(N). Це однаково для проблеми шкарпетки (також O(N), якщо вам потрібен лише один етап розповсюдження (я запропонував кілька кроків тільки тому, що люди в процесі розрахунків погані - достатньо одного кроку, якщо ви роздасте md5(color, length, pattern, ...), то є a досконалий хеш з усіх атрибутів)).

Зрозуміло, що не можна піти швидше, ніж O(N), тому ми досягли оптимальна нижня межа.

Хоча результати не точно однакові (в одному випадку, лише булеві, а в іншому - пари шкарпеток), асимптотичні складності однакові.


2180
2017-10-19 20:47



Це саме те, що я роблю! Я роблю купи залежно від стилю відкриття носка (я тільки білий), що дає мені достатньо "ковшів", щоб швидко відповісти кожному з них. - Scott Chamberlain
Я спробував це зі своїми шкарпетками (я легко отримав 30+ пар), і людина це швидкий. Одна з проблем, яку я знайшов, - це коли я не можу мати достатньо хеш-алгоритму (у мене є безліч білих шкарпеток без будь-якого шаблону), щоб стати важко. У цьому випадку, як би це було оптимальним способом? - NothingsImpossible
@ Неможливо, що атаки зіткнень хеш-холу виглядають як для бідного веб-сервера! Чи білі шкарпетки відрізняються деяким атрибутом? Там повинно бути щось, що ви можете розподілити їх. Інакше ви могли б просто сформувати пари довільно. - usr
Це Radix Sort, я згоден, це правильна відповідь. @MarkPeters Я не думаю, що вам потрібен таблиця пошуку. Один лінійний прохід через шкарпетки може перетворити шкарпетки на векторних чисел, роблячи відображення "сеточного шкарпетки" на відбиток тривіальним. Шкарпетки можуть бути прив'язані до векторів з рядком, так що вам не потрібен інший лінійний прохід в кінці. - Pointy
Хлопчик, я пішов до коледжу з власне PairIDs. Вона була пришита на кожну пару шкарпеток з ниткою: 1, 2, 3, 4 ... - Ryan Lundy


Оскільки архітектура людського мозку абсолютно відрізняється від сучасного ЦП, це питання не має практичного сенсу.

Люди можуть перемогти над алгоритмами процесора, використовуючи той факт, що "пошук відповідної пари" може бути однією операцією для набору, який не є надто великим.

Мій алгоритм:

spread_all_socks_on_flat_surface();
while (socks_left_on_a_surface()) {
     // Thanks to human visual SIMD, this is one, quick operation.
     pair = notice_any_matching_pair();
     remove_socks_pair_from_surface(pair);
}

По крайней мере, це те, що я використовую в реальному житті, і я вважаю це дуже ефективним. Проблема полягає в тому, що вона вимагає рівної поверхні, але це зазвичай рясні.


523
2018-05-27 19:13



коли кількість шкарпеток збільшується, SIMD людини стає не кращим, ніж процесор. - Lie Ryan
Краща відповідь, ІМО. Хоча це весело і розумно (і доцільно для SO), щоб зменшити щоденну проблему до алгоритму комп'ютера, для набору таких малих, як ~ 60 шкарпеток, є набагато більше сенсу використовувати силу роздільної здатності очі людини / мозку. - drug_user841417
@LieRyan Якщо шкарпетки рівномірно розподілені, ви закінчите помітити пару в будь-якому досить невеликому наборі шкарпеток через парадокс до дня народження (якщо ви не можете відрізнити кольори до довільної точності, які я сумніваюся), так що вузьке місце тут не буде алгоритм співставлення кольорів людини, але етап розповсюдження. - Thomas
@ dpc.ucore.info Ні, тому що вони мають різні тканини манжети, довжини манжети, загальні довжини і відтінки чорного кольору (моя дружина, ймовірно, фізично пошкодить мене за останню). - Christian
Ви краще сподіваєтеся, що у вас є рівне число шкарпеток, інакше ви збираєтеся складатися шкарпетки на довгий час ... - Patrick James McDougle


Випадок 1: Всі шкарпетки ідентичні (це те, що я роблю в реальному житті, до речі).

Виберіть будь-які два з них, щоб зробити пару. Постійний час.

Справа 2: Існує постійна кількість комбінацій (власність, колір, розмір, текстура тощо).

Використовуйте Родс сортувати. Це лише лінійний час, оскільки порівняння не є обов'язковим.

Справа 3: Кількість комбінацій невідомо заздалегідь (загальний випадок).

Ми маємо провести порівняння, щоб перевірити, чи париться два шкарпетки. Виберіть один з O(n log n) алгоритми сортування на основі порівняння.

Однак в реальному житті, коли число шкарпеток відносно невелике (постійне), ці теоретично оптимальні алгоритми не працюють б добре. Це може зайняти ще більше часу, ніж послідовний пошук, який теоретично вимагає квадратного часу.


231



> Це може зайняти ще більше часу, ніж послідовний пошук, який теоретично вимагає квадратного часу. Так, саме тому я ненавиджу це робити, можливо, я повинен викинути всі мої шкарпетки і почати з випадку 1. - Nils
Я вважаю легше мати всі ті ж шкарпетки, а також. Кожну пару років я купую 10 із цих 6 пачок шкарпеток, коли вони продаються, і викидаю всі мої старі шкарпетки. Просто легше зіставити однакові шкарпетки, і вони виглядають краще, ніж старі святі шкарпетки. Таким чином, найпростіший спочатку у верхній частині купи є найшвидшим для мене. - Michael D. Kirkpatrick
нижня сторона, що має всі однакові шкарпетки, полягає в тому, що вони схильні до віку з різними показниками. Тому ви все-таки в кінцевому підсумку намагаються підібрати їх відповідно до того, наскільки вони носяться. (що важче, ніж просто відповідність за шаблоном) - SDC
Проблема з наявністю 60 пар ідентичних шкарпеток ", тому що це полегшує створення сполучень" - це те, що створює враження, що ви працюєте з комп'ютерами. - Steve Ives
Випадок 1 не є постійним часом, коли відбувається операція, наприклад, складені пари разом. У цьому випадку це лінійний час з найменшим постійним чинником (доказ якого залишається як вправ для читача). Один не може в один і той же час скласти одну пару і відро, повне шкарпеток. Однак він лінійно масштабується. За законом Амдаля, він має необмежений прискорення, ігноруючи накладні витрати. За законом Густафсона можна скласти стільки пар, скільки потрібно для того, щоб скласти одну пару з достатньою кількістю робітників (кількість яких залишається як вправ для читача), ігноруючи накладні витрати. - acelent


Не алгоритмічна відповідь, але "ефективна", коли я це роблю:

  • крок 1) відкинь всі існуючі шкарпетки

  • крок 2) перейти до Walmart і купувати їх пакетами 10 - н пакета білі та м пакети чорного кольору. Немає потреби в інших кольорах у повсякденному житті життя

Але час від часу я повинен це зробити ще раз (втрачені шкарпетки, пошкоджені шкарпетки тощо), і мені дуже не хочеться дуже добре відкидати шкарпетки (і я хотів, щоб вони продовжували продавати ту ж увагу на шкарпетки!), Тому я нещодавно взяв інший підхід.

Алгоритмічна відповідь:

Розглянемо, ніж якщо ви намалюєте лише один носок для другої купи шкарпеток, як ви робите, ваші шанси знайти відповідний шкарпетки в наївному пошуку досить низькі.

  • Отже, візьміть п'ять з них випадковим чином, і запам'ятайте їх форму або довжину.

Чому п'ять? Як правило, люди добре пам'ятають від п'яти до семи різних елементів у робочій пам'яті - трохи схожий на людський еквівалент a RPN стека - п'ять є безпечним дефолтом.

  • Візьміть із стіни 2n-5.

  • Тепер подивіться на збіг (візуальний підбір зображень - люди добре в цьому з невеликою кількістю стеків) всередині п'яти, які ви намалювали, якщо ви не знайшли його, а потім додайте це до ваших п'яти.

  • Продовжуйте випадково підбирати шкарпетки зі стеків і порівняти з вашими 5 + 1 шкарпетками для матчу. Як ваш стек зростає, це зменшить вашу продуктивність, але підвищить ваші шанси. Набагато швидше.

Не соромтеся записати формулу, щоб розрахувати, скільки зразків ви повинні намалювати на 50% шанс матчу. IIRC це гіпергеометричний закон.

Я роблю це щоранку і рідко потрібно більше трьох нічиїх - але я маю n подібні пари (близько 10, дають або втрачають) m формлені білі шкарпетки. Тепер ви можете оцінити розмір мого купою акцій :-)

До речі, Я виявив, що сума транзакційних витрат на сортування всіх шкарпеток кожного разу, коли мені потрібна пара, була набагато меншою, ніж одноразове виконання і обов'язкові носки. Практично вчасно працює краще, тому що вам не потрібно зв'язувати шкарпетки, а також зменшується граничний прибуток (тобто ви продовжуєте шукати ті два або три шкарпетки, що коли десь у пральній машині і що вам потрібно щоб закінчити відповідність ваших шкарпеток, і ви втрачаєте час на це).


144



Підтримати "неалгоритмічну" відповідь. Це саме те, що я роблю, і це чудово працює. Проблема з заміною не є проблемою, якщо ви "обертаєте" носок, розмістивши мити шкарпетки в задній частині і потягнувшись з переднього боку ящика вранці. Всі шкарпетки носять рівномірно. Коли я починаю помічати деякий знос на одному, я поклав у список покупок, щоб повністю замінити цілий клас шкарпеток. Для старих шкарпеток я надаю найкращі 20% доброї волі (прив'язані до бакалійного мішка, щоб вони не змішувались назад), і віддаляйте решту. Ви не витрачаєте шкарпетки, на даний момент, 80% лише 6 місяців залишаються в будь-якому випадку. - FastAl
BTW (1) Прив'язка ваших шкарпеток призводить до еластичного, один, що зберігається розтягнутий, і воля зазнає значно швидше. Обмежування видів унікальних шкарпеток, які ви робите, зобов'язує вас не забороняти. (2) Недоліком обмеження унікальних шкарпеток є те, що для людей з певними модними проблемами метод може бути непридатним. - FastAl
Я прийшов сюди, щоб опублікувати вашу "неалгоритмічну" відповідь. Як і в справжній комп'ютерній техніці, більшість людей ніколи не приділяють достатньої уваги даних та їх структурі. - bkconrad
Я використовую цей алгоритмічний підхід щоранку, і це працює як чарівність! Крім того, я знімаю носилі шкарпетки в іншу купу, щоб потім викинути пізніше (на жаль, їм вдалося знову дістатись до оригінальної купи, перш ніж знайти час, щоб його смітити). - Donatas Olsevičius
«N пакет білого і м пакетів чорного кольору. Немає необхідності в інших кольорах в житті в повсякденному житті »Хорошим стандартним правилом для вибору простого носка є те, що вони повинні відповідати як кольору брюк, так і колір поясу. З цієї причини найбільш часто використовувані кольори, ймовірно, будуть чорними, синіми, сірими та коричневими. Важко повірити, що потрібні багато білих шкарпеток. - Andrea Lazzarotto


Що я роблю, це те, що я забираю перший шкарпетки і поклав його (скажімо, на краю білизни). Потім я забираю інший носок і перевіряю, чи це так само, як і перший носок. Якщо це так, я видалю їх обох. Якщо це не так, я ставлю його поруч із першим носком. Потім я забираю третій шкарпетки та порівнюю це з першими двома (якщо вони все ще там). І т. Д.

Цей підхід досить легко реалізувати в масиві, якщо передбачити, що "видалення" шкарпеток - це можливість. Насправді, вам навіть не потрібно "видаляти" шкарпетки. Якщо вам не потрібна сортування шкарпеток (див. Нижче), то ви можете просто перемістити їх навколо і закінчити масив, у якому всі шкарпетки розташовані парами в масиві.

Припускаючи, що єдиною операцією для шкарпеток є порівняння для рівності, цей алгоритм в основному ще є n2 алгоритм, хоча я не знаю про середній випадок (ніколи не навчився його розрахувати).

Сортування, звичайно, підвищує ефективність, особливо в реальному житті, де ви легко можете "вставити" носок між двома іншими шкарпетками. У обчисленні те ж саме можна досягти деревом, але це додатковий простір. І, звичайно, ми повертаємося до NlogN (або трохи більше, якщо є декілька шкарпетків, однакових за критеріями сортування, але не з тієї самої пари).

Крім того, я не можу нічого думати, але цей метод, здається, досить ефективний у реальному житті. :)


92



Це теж те, що я роблю (зауважте, що якщо ви просто залиште пробіли, то вставки також є O (1)), але це слабко зрівнює з теоретично великою кількістю шкарпеток. - Mooing Duck
ваги погано з теоретично великою кількістю види шкарпетки - Steven Lu
@StevenLu - як я вже сказав - це n * n або nLogn, в залежності від того, ви сортуєте його чи ні. Таким чином, вона масштабується так само погано, як і будь-який алгоритм сортування. Якщо ви хочете швидше, набрати номер і скористатися сортуванням radix. - Vilx-
Це, по суті, зберігає знайдені, але не підібрані шкарпетки в хеш-основі пошуку. Ідеальний хеш - це O (n), але якщо у вас є достатньо шкарпеток, хеш починає дегенеруватися, відповідно складніше. - Jon Hanna
Яке значення вкладає носок між ще двома іншими шкарпетками, щоб досягти мети створення шкарпеток? немає потужності шкарпеток. : -x - JoeBrockhaus


Це запитує неправильне питання. Правильне запитання: чому я провожу час сортування шкарпеток? Скільки це коштує на щорічній основі, коли ви цінуєте свій вільний час для вашої грошової одиниці X?

І частіше, це не просто будь-який вільний час, це все ранок вільний час, який ви можете витратити в ліжко, або посипати свою каву, або залишити трохи рано, а не потрапити в трафік.

Дуже добре робити крок назад і подумати про проблему.

І є спосіб!

Знайдіть носок, який вам подобається. Враховуйте всі відповідні особливості: кольори в різних умовах освітлення, загальна якість та довговічність, комфорт при різних кліматичних умовах та поглинання запаху. Також важливо, щоб вони не втрачали еластичність у зберіганні, тому натуральні тканини хороші, і вони повинні бути доступними у пластиковій упаковці.

Краще, якщо немає різниці між носками лівої та правої ноги, але це не критично. Якщо шкарпетки є симетричними зліва направо, пошук пари - операція O (1), а сортування шкарпеток - приблизна операція O (M), де M - кількість місць у вашому домі, які ви засмітили носками, в ідеалі - деякі мала постійна кількість

Якщо ви вибрали привабливу пару з різними лівими і правильними носками, роблячи повний сорт ковша на відро з лівим і правом ногами, беруть O (N + M), де N - кількість шкарпеток, а M - таке ж, як вище. Хтось інший може дати формулу для середніх ітерацій пошуку першої пари, але найгіршим випадком для пошуку пари з сліпим пошуком є ​​N / 2 + 1, що стає астрономічно малоймовірним випадком для розумного N. Це може бути збільшено за допомогою розширеного зображення алгоритми розпізнавання та евристики при скануванні купи несортованих шкарпеток з Mk1 Eyeball.

Отже, алгоритм досягнення ефективності сполучення носівок O (1) (за умови симетричного носка):

  1. Потрібно оцінити, скільки пари шкарпеток вам знадобляться на все життя, або, можливо, поки ви не вийдете на пенсію і не перейдете до більш теплого клімату, і вам не доведеться носити шкарпетки. Якщо ви молоді, ви також можете оцінити, скільки часу це потрібно, перш ніж у нас всі працюватимуть в нашому домі роботів для сортування шкарпеток, і вся проблема стає невідповідною.

  2. Ви повинні з'ясувати, як можна замовляти вибраний носок навалом, і скільки це коштує, і вони доставляють.

  3. Замовте шкарпетки!

  4. Позбутися від старих шкарпеток.

Альтернативний крок 3 передбачає порівняння витрат на придбання такої кількості, можливо, дешевих шкарпеток кількох пар одночасно протягом багатьох років та додавання витрат на сортування шкарпеток, але прийміть своє слово: покупка оптом дешевше! Крім того, шкарпетки на складах збільшують вартість за швидкістю інфляції цін на акції, що більше, ніж на багато інвестицій. Потім знову є вартість зберігання, але шкарпетки дійсно не займають багато місця на верхній полиці шафи.

Проблема вирішена. Отже, просто здобувайте нові шкарпетки, кидайте / жертвуйте своїх старих і живете щасливо, коли знаєте, що ви заощаджуєте гроші і час кожен день на все життя.


50



Тривалість життя (припускаючи 75 років) поставляє шкарпетки (припускаючи, що ви вичерпаєте 4 пари на місяць, що становить 3600 пар) займе (припускаючи, що нова пари шкарпеток займає 20 кубічних дюймів) загалом 1 1/2 кубічних ярдів. Це величезна кількість простору. Припускаючи, що вони доставлять його вам у коробці, яка приблизно є кубом, ця ячейка буде приблизно 3 фути 4 дюйма на боці. - AJMansfield
@AJMansfield вірна проблема. Однак я не згоден з кількома вашими цифрами. Я б узяв понад 40 років (25 ... 65) (час між тим, хто не живе у батьків / гуртожиток / тощо, і на пенсію, див. Вище). Крім того, я думаю, одна пара більше займає 0,5x4x6 дюймів у оригінальній упаковці. Ці цифри приносять ваш простір досить швидко! - hyde
Крок 4 необов'язково марнотратний, -1. - Dan Bechard
Посібник для інших, котрі можуть збити з погляду вимірювань AJ Mansfield, переведення в метрику: »займеться (припускаючи, що нова пари шкарпеток займає 327 см³) загалом 1,14 м³. Це величезна кількість простору. Припускаючи, що вони доставлять його вам у коробці, яка приблизно є кубом, така коробка буде близько 1,04 м на боці. - Joey


Теоретичним обмеженням є O (n), тому що вам потрібно торкнутися кожного носка (якщо деякі з них вже не є парними).

Ви можете досягти O (n) з Родс сортувати. Вам просто потрібно вибрати деякі атрибути для відра.

  1. Спочатку ви можете вибрати (її, мій) - розділити їх на 2 паль
  2. потім використовуйте кольори (може мати будь-який порядок для кольорів, наприклад, в алфавітному порядку за кольором) - розбити їх на купи за кольором (не забувайте зберігати початковий порядок з кроку 1 для всіх шкарпеток у тій самій нагромаді);
  3. потім довжина носка,
  4. потім текстура ....

Якщо ви можете вибрати обмежену кількість атрибутів, але достатньо атрибутів, які можуть однозначно ідентифікувати кожну пару, ви повинні зробити це в O (k * n), тобто O (n), якщо ми можемо розглянути k обмежене.


47



Шкарпетки часто поставляються в 4 пакетах і більше, оскільки це дешевше, але це також робить їх незмінними. Щоб протистояти цьому, моя дружина набиває крихітку відмітку на кожну нову пару шкарпеток, я купую. Знак має інший колір для кожної пари чи іншої форми, якщо вона вичерпується кольором. За допомогою цього підходу вам навіть не потрібний обмежений набір атрибутів. Просто пришийте унікальний номер на кожній парі. :) Для додаткових очок використовуйте бінарний файл. - Vilx-
@ Вілкс-ЧОМУ!!? Чи не цілком сприймається, що вони не відрізняються? - flup
@ flup - Я думаю, що цілком слід продати у більших розшаруваннях. :) Що стосується мене, це допомагає носити їх у парах. В іншому випадку я можу закінчити з трьома дуже носити шкарпетки та один зовсім новий. Kinda дурний. - Vilx-
Я не погоджуюсь з розрахунком O (n). Що таке $ k $? $ k $ - це кількість атрибутів. Я б стверджував, що $ k $ - $ O (log n) $, тому що він повинен бути достатнім, щоб однозначно ідентифікувати кожну пару. Якщо у вас 2 пари (чорно-біле), то достатньо кольору ($ k = 1, n = 2 $). Якщо у вас одна пара чорного, коротка; одна пара чорна, довга; одна пара біла, коротка; і одна пара білих, довгих - тоді $ k = 2, n = 4 $. Тоді, якщо обмежити $ k $, ми одночасно обмежимо $ n $. Якщо ми збираємося обмежити $ n $, то розрахунок замовлення більше не має сенсу. - emory
@mory, я думаю, що ви шукаєте зворотний бік, а не $ символ, щоб зробити ваш матеріал виглядати кодом-y. - Xymostech