Разработать коммутативную инъективную функцию между любым (ограниченным) бесконечным множеством и его неупорядоченными парами

18

Связано, но это требует только натуральных чисел и не должно быть коммутативным

Функция сопряжения Кантора описана в этой статье Википедии . По сути, это такая операция, что, когда она применяется к двум значениям X и Y, можно получить исходные значения X и Y с учетом результата.

Ваша задача - разработать две функции: одну, которая выполняет, X, Y -> Zа другую, которая выполняет Z -> X, Y. Вот подвох: X, Y -> Zдолжен быть коммутативным. Это означает, что Z -> X, Yвы не сможете определить, был ли ввод X, Yили Y, X.

Формальное определение этого вызова будет:

Выберите счетное бесконечное множество S чисел.
Разработайте две функции, которые выполняют следующие задачи:

  • Если дана неупорядоченная пара значений в S, вернуть значение в S
  • Получив возвращаемое значение из исходной функции, верните неупорядоченную пару значений, которая вычисляется во входное целое число при прохождении через первую функцию. Меня не волнует поведение этой обратной функции, если входные данные не являются возвращаемым значением из первой функции.

Требования

  • Результат должен быть одинаковым между пробегами.
  • {a, a} неупорядоченная пара

Примечание: ваш ответ с большей вероятностью получит от меня отклик, если вы предоставите доказательство, но я проверю ответы, когда доберусь до него, и опрошу его, как только буду уверен, что это сработает.

HyperNeutrino
источник
Разве это не подходит лучше для puzzling.stackexchange.com ?
Якуб,
2
@Jakube Не обязательно, так как вы обязаны писать код.
г-н Xcoder
Я предполагаю, что пары уникальны, но числа, используемые в этих парах, не? Так, когда 1,2одна из пар, 1,3также может быть потенциальной парой (обе используют 1)?
Кевин Круйссен,
@KevinCruijssen Я не уверен, что вы имеете в виду
HyperNeutrino
@Giuseppe Обратное не обязательно должно быть в состоянии вернуть правильный порядок; это просто, что для функции fи ее обратное g, sorted((x, y))должно быть таким же, какsorted(g(f(x, y)))
HyperNeutrino

Ответы:

13

Haskell , 65 + 30 = 95 байт

a#b=length.fst$span(<(max a b,min a b))[(a,b)|a<-[1..],b<-[1..a]]

Попробуйте онлайн!

([(a,b)|a<-[1..],b<-[1..a]]!!)

Попробуйте онлайн!


Примечание. Когда две функции могут совместно использовать код, это только 75 байтов:

(l!!)
a#b=length.fst$span(<(max a b,min a b))l
l=[(a,b)|a<-[1..],b<-[1..a]]

Попробуйте онлайн! Домен является положительными целыми числами. Функция (#)выполняет сопряжение, функция (l!!)обратная. Пример использования: Как (#) 5 3и (#) 3 5выход 12, и (l!!) 12выходы (5,3).

Это работает путем явного перечисления всех отсортированных пар в бесконечном списке l:

l = [(1,1),(2,1),(2,2),(3,1),(3,2),(3,3),(4,1),(4,2),(4,3),(4,4),(5,1),(5,2),(5,3),(5,4),(5,5),(6,1), ...`

Кодировка - это просто индекс в этом списке.

Laikoni
источник
по ОП, общий код должен быть посчитан дважды
гордый haskeller
5

Pyth , 8 + 6 = 14 байтов

ij\aSQ16

    SQ   # Sort the input
 j\a     # join with "a"
i     16 # convert from base 16 to base 10

Попробуйте онлайн!

c.HQ\a

 .HQ     # convert from base 10 to 16
c   \a   # split on "a"

Попробуйте онлайн!
Домен: целые положительные числа.

прут
источник
хороший подход! +1
HyperNeutrino
4
Не работает для многих номеров, таких как 2и 10например (которые находятся в домене)
Emigna
Конечно. Пример1 , Пример2
Emigna
Предполагается, что 2-я функция работает для любого значения в S, а не только для того, которое было сгенерировано первой функцией (я сделал ту же ошибку).
Arnauld
4

Желе , 8 + 11 = 19 байт

Откат, так как алгоритм Рода не работал.

Это работает в области положительных целых чисел.

Принимает xи yкак 2 аргумента, не имеет значения, в каком порядке, возвращает z.

»’RSð+ð«

Попробуйте онлайн!

Берет zи возвращает[min(x, y), max(x, y)]

R€Ẏ,Rx`$ị@€

Попробуйте онлайн!

Эрик Outgolfer
источник
1
Почему отрицательные голоса? Это не алгоритм Рода.
Эрик Outgolfer
4

JavaScript (ES7), 44 байта

(x,y)=>x>y?x*x+y:y*y+x
z=>[x=z**.5|0,y=z-x*x]

Отображает неотрицательные целые числа на их подмножество.

Нил
источник
4

C (gcc) , 36 + 39 = 75 байт

Спасибо @tsh за сохранение двух байтов.

Домен неотрицательных целых чисел.

p(x,y){return y>x?p(y,x):-~x*x/2+y;}

Берет xи yвозвращает z.

u(int*r){for(*r=0;r[1]>*r;r[1]-=++*r);}

Принимает двухэлементный intмассив. Второй элемент должен быть установлен zдо вызова. После звонка rсодержится xи y.

Попробуйте онлайн!

nwellnhof
источник
(x+1)->-~x
TSH
3

Желе , 13 11 байт

пара натуральных чисел в натуральное число, 5 байтов

Ṁc2+Ṃ

Попробуйте онлайн!

целое положительное число в пару натуральных чисел, 6 байтов

ŒċṀÞị@

Попробуйте онлайн!

Алгоритм

Если мы отсортируем множество всех неупорядоченных пар натуральных чисел по их максимуму, а затем по их сумме, мы получим следующую последовательность.

{1,1}, {1,2}, {2,2}, {1,3}, {2,3}, {3,3}, {1,4}, {2,4}, {3 , 4}, {4,4}, {1,5}, {2,5}, {3,5}, {4,5}, {5,5},…

Первая функция берет пару {x, y} и находит ее индекс в этой последовательности.

Вторая функция принимает положительное целое число z и возвращает z- й элемент последовательности.

Обратите внимание, что это отображение такое же, как в ответе Jelly @ EriktheOutgolfer .

Как это устроено

Ṁc2+Ṃ   Main link. Argument: [x, y]
        Let m = max(x, y) and n = min(x, y).

Ṁ       Maximum; yield m.
 c2     2-combinations; yield mC2 = m(m-1)/2.
        Note that there's one pair with maximum 1 ({1,1}), two pairs with maximum 2
        ({1,2}, {2,2}), etc., so there are 1 + 2 + … + (m-1) = m(m-1)/2 pairs with
        maximum less than m.
    Ṃ   Minimum; yield n.
        Note that {x,y} is the n-th pair with maximum m.
   +    Add; yield mC2 + n.
        This finds {x,y}'s index in the sequence.
ŒċṀÞị@  Main link. Argument: z

Œċ      2-combinations w/replacement; yield all pairs [x, y] such that x ≤ y ≤ z.
  ṀÞ    Sort by maximum.
    ị@  Retrieve the pair at index z (1-based).
Деннис
источник
2
Пояснения пожалуйста. Я не уверен, что это верно ...
Эрик Outgolfer
Я добавил алгоритм.
Деннис
Что-то не очень хорошо для меня ... хотя я не уверен, что это тоже недействительно. По сути, это не очень хорошо, если вы используете оба cи Œċ... хотя я могу ошибаться. Кстати, это был мой ответ, что вы переиграли> _>
Эрик Outgolfer
Разница минимальна для пар. Если C вычисляет комбинации без замены и combinations вычисляет комбинации с помощью, nƇ2 = nC2 + n .
Деннис
2

Mathematica (35 + 53) = 78 байт

((x=Min[#])+(y=Max[#]))(x+y+1)/2+y&

(i=Floor[(-1+Sqrt[1+8#])/2];{#-i(1+i)/2,i(3+i)/2-#})&

Это одна хорошо известная квадратичная функция сопряжения для Z <-> ZxZ в сочетании с Min и Max, чтобы сделать ее упорядоченной.

Келли Лоудер
источник
2

Рубин, 66 байт

f=->x,y{2**~-x|2**~-y}
g=->n{x,y=(1..n).select{|i|n[i-1]>0};[x,y||x]}

Я пытаюсь найти способ хитро выбрать бесконечный набор, чтобы сделать это проще, это лучшее, что у меня есть до сих пор.

Определим f (x, y) = 2 x-1 поразрядно или 2 y-1 . Домен состоит из набора, определенного рекурсивно как содержащего 1,2, и всех чисел, которые могут быть получены путем вызова f на числах в наборе (обратите внимание, что f (1,1) = 1 и f (2,2) = 2, поэтому 1 и 2 имеют обратные). Все получающиеся числа имеют одну или две единицы в их двоичном разложении, причем индексы единиц соответствуют числам в наборе. Мы можем получить оригинальную неупорядоченную пару, взяв индексы. Если есть только один 1, это означает, что элементы пары равны.

Например, f (3,5) равно 20, потому что 20 равно 10100 в основании 2, которое имеет 1 в 3-м и 5-м наименее значимых местах.

histocrat
источник
Спасибо, S на самом деле является подмножеством этой последовательности OEIS, потому что он включает в себя только числа, чьи 1 имеют индексы в S.
гистократ
ах да, конечно. Ну, ни одна другая последовательность не соответствует первым нескольким слагаемым (до 32).
Джузеппе
Добавьте 0 к S, и вы можете сохранить несколько декрементов.
nwellnhof
2

Ява 8, 153, 146, 141, 137 + 268, 224, 216, 205 байт.

Парная функция

a->{String f="";for(int i=(f+a[0]).length(),c=0,j;i>0;i-=c,f+=c,c=0)for(j=1;j<10;c+=i-j++<0?0:1);return new Integer(a[0]+""+a[1]+"0"+f);}

Попробуйте онлайн!

Функция удаления

r->{String a=r+"",t=a.substring(a.lastIndexOf('0')+1);int l=0,i=l,o=t.length();for(;i<o;l+=r.decode(t.charAt(i++)+""));return new int[]{r.decode(a.substring(0,l)),r.decode(a.substring(l,a.length()-o-1))};}

Попробуйте онлайн!

Роберто Грэм
источник
1
Вы можете сыграть в гольф несколькими частями. В парной функции: int i=(""+a[0]).length()может быть int i=(f+a[0]).length(); пространство между c=0,j;i>0;может быть удалено; a[0].parseIntможет быть new Integer. В функции deair: все три r.parseIntмогут быть r.decode; и вы могли бы сделать переменную int для t.length(), так как вы используете его дважды.
Кевин Круйссен,
1

05AB1E , 6 + 11 = 17 байт

Порт моего желе ответа.

Домен: целые положительные числа.

Принимает список в [x, y]качестве входных данных, возвращает z.

{`<LO+

Попробуйте онлайн!

Принимает положительное целое число в zкачестве входных данных, возвращает [min(x, y), max(x, y)].

L2ã€{RÙR¹<è

Попробуйте онлайн!

-5 спасибо Эмигне .

Эрик Outgolfer
источник
Ваша вторая программа может сохранить 5 байтов с помощью L2ã € {RÙRI <è
Emigna
@ Emigna Хороший трюк с 2ã€{RÙR!
Эрик Outgolfer
1

JavaScript, 72 байта

f=a=>eval('0x'+a.sort().join`a`)
g=n=>n.toString(16).split`a`.map(x=>+x)

Работает для натуральных чисел (в теории). Идея довольно проста: отсортировать два числа в некотором (магическом) порядке, соединить их в виде строки буквой "a", проанализировать как шестнадцатеричное целое число.

ТТГ
источник
1

MATL, 6 + 8 = 14 байтов

Функция кодирования, принимает два входа n, m. Выводит произведение n-го простого и m-го простого.

,iYq]*

шаги:

  • , - Делай дважды
  • i - Push-ввод
  • Yq - Поп-ввод, толчок ввода
  • ]* - Конец делай дважды, вставляй оба простых числа и выдвигай товар

Функция декодирования, занимает один вход м. Выводит число простых чисел ниже каждого из простых множителей n.

iYf"@Zqn

шаги:

  • i - Push-ввод
  • Yf - Поп ввод, толчок массива простых факторов
  • " - для п в массиве
  • @Zq - толкать массив простых чисел ниже n
  • n - Поп массив, толчок длины массива

Это коммутативно, потому что умножение коммутативно, и инъективно, потому что простые факторизации уникальны. Не то чтобы это не на целые числа.

Дейв
источник
0

шелуха , 5 + 3 = 8 байт

Я действительно надеюсь, что выполнил задание правильно, я вижу некоторые удаленные ответы, которые кажутся мне действительными ...

Пары натуральных чисел в одно положительное целое число:

¤*!İp

Попробуйте онлайн!

Он работает, беря числа по заданным индексам (1-индексированные) из списка простых чисел и умножая их.

Результат первой функции для пары натуральных чисел:

mṗp

Попробуйте онлайн!

Мы разлагаем входное число и возвращаем индекс в списке простых чисел всех (обоих) его факторов.

Работал пример

В (4,1)качестве стартовой пары мы берем четвертое и первое простые числа (7,2)и умножаем их → 14. Это умножение делает функцию независимой порядка двух элементов.

Начиная с 14, мы разлагаем его (2,7)и возвращаем индексы 2и 7в списке простых чисел → (1,4).

Лео
источник
На самом деле, глядя на удаленный ответ от Арно, его алгоритм еще лучше, и портирование его на Husk приведет к 6 байтам ... Может ли кто-нибудь подтвердить, является ли его решение (и мое тоже) верным или нет?
Лев
Не работает для простых чисел (которые находятся в области натуральных чисел)
Emigna
@ Emigna вторая функция не имеет, но простые числа никогда не возвращаются первой ...
Лев
Ваш домен является положительными целыми числами, поэтому оба метода должны работать для положительных целых чисел. РЕДАКТИРОВАТЬ: или, по крайней мере, это было требованием. Текущие правила, кажется, разрешают подмножество домена.
Emigna
0

C # , 80 байт (38 + 42)


Данные

кодировщик

  • Введите Int32 l число
  • Введите Int32 r число
  • Выходные данные Int64 Оба целых объединены

дешифратор

  • Входное Int32 v значение
  • Выходные данные Int32[] Массив с двумя исходными целыми числами.

Golfed

// Encoder
e=(l,r)=>{return(long)l<<32|(uint)r;};

// Decoder
d=v=>{return new[]{v>>32,v&0xFFFFFFFFL};};

Ungolfed

// Encoder
e = ( l, r ) => {
    return (long) l << 32 | (uint) r;
};

// Decoder
d = v => {
    return new[] {
        v >> 32,
        v & 0xFFFFFFFFL };
};

Ungolfed читабельный

// Encoder
// Takes a pair of ints
e = ( l, r ) => {

    // Returns the ints fused together in a long where the first 32 bits are the first int
    // and the last 32 bits the second int
    return (long) l << 32 | (uint) r;
};

// Decoder
// Takes a long
d = v => {

    // Returns an array with the ints decoded where...
    return new[] {

        // ... the first 32 bits are the first int...
        v >> 32,

        // ... and the last 32 bits the second int
        v & 0xFFFFFFFFL };
};

Полный код

using System;
using System.Collections.Generic;

namespace TestBench {
    public class Program {
        // Methods
        static void Main( string[] args ) {
            Func<Int32, Int32, Int64> e = ( l, r ) => {
                return(long) l << 32 | (uint) r;
            };
            Func<Int64, Int64[]> d = v => {
                return new[] { v >> 32, v & 0xFFFFFFFFL };
            };

            List<KeyValuePair<Int32, Int32>>
                testCases = new List<KeyValuePair<Int32, Int32>>() {
                    new KeyValuePair<Int32, Int32>( 13, 897 ),
                    new KeyValuePair<Int32, Int32>( 54234, 0 ),
                    new KeyValuePair<Int32, Int32>( 0, 0 ),
                    new KeyValuePair<Int32, Int32>( 1, 1 ),
                    new KeyValuePair<Int32, Int32>( 615234, 1223343 ),
                };

            foreach( KeyValuePair<Int32, Int32> testCase in testCases ) {
                Console.WriteLine( $" ENCODER: {testCase.Key}, {testCase.Value} = {e( testCase.Key, testCase.Value )}" );
                Console.Write( $"DECODING: {e( testCase.Key, testCase.Value )} = " );
                PrintArray( d( e( testCase.Key, testCase.Value ) ) );

                Console.WriteLine();
            }

            Console.ReadLine();
        }

        public static void PrintArray<TSource>( TSource[] array ) {
            PrintArray( array, o => o.ToString() );
        }
        public static void PrintArray<TSource>( TSource[] array, Func<TSource, String> valueFetcher ) {
            List<String>
                output = new List<String>();

            for( Int32 index = 0; index < array.Length; index++ ) {
                output.Add( valueFetcher( array[ index ] ) );
            }

            Console.WriteLine( $"[ {String.Join( ", ", output )} ]" );
        }
    }
}

релизы

  • v1.0 - 80 bytes- Исходное решение.

Примечания

  • Никто
auhmaan
источник
0

Python: 41 + 45 = 86

кодировщик: 41

e=lambda*x:int('1'*max(x)+'0'+'1'*min(x))
e(4, 3), e(3,4)

(11110111, 11110111)

декодер: 45

d=lambda z:[len(i)for i in str(z).split('0')]
d(11110111)

[4, 3]

Старая попытка:

Python: 114: 30 + 84

кодировщик: 30

принимает 2 целых числа, возвращает строку

e=lambda*x:2**max(x)*3**min(x)
e(3, 4), e(4, 3)

(432, 432)

декодер: 86

def d(z):
 x=y=0
 while 1-z%2:
  x+=1
  z/=2
 while 1-z%3:
  y+=1
  z/=3
 return x,y
d(432)

4, 3

декодер2: 120

еще одна попытка с генератором пониманий и суммы

def d(z):
 x=sum(1 for i in range(z)if not z%(2**i))-1
 z/=2**x
 return x,sum(1 for i in range(int(z))if not z%(3**i))-1
Мартен Фабре
источник
1
на основании второй попытки: e=lambda*x:10**sum(x)-10**min(x);d=lambda z:map(z .count,'09'); TIO
TSH
@tsh очень мило. Я адаптирую его позже, или вы можете представить свой собственный ответ
Maarten Fabré