Mappatura di 40 numeri interi univoci su 41 e ritorno

È possibile, ci sono 960/41 serie in più di 41 numeri rispetto a serie di 40 numeri. Decidi di qualsiasi mappatura arbitraria.

Come esempio di mappatura algoritmica, considereremo un problema esteso: l'aggiunta di N numeri a partire da M a un set (il problema originale può essere risolto aggiungendo 1 numero a partire da 1 all'insieme).

Se M non è presente nel set, aggiungi M al set e poi aggiungi i numeri N-1 a partire da M + 1 al set. Se M è presente nel set, rimuovi M dal set e aggiungi i numeri N + 1 a partire da M + 1 al set.

Per decodificare, dobbiamo rimuovere N numeri a partire da M da un set (il problema originale può essere risolto rimuovendo 1 numero a partire da 1).

Se M è presente nell'insieme, rimuovere M dall'insieme e quindi rimuovere i numeri N-1 a partire da M + 1. Se M non è presente nel set, aggiungi M al set e quindi rimuovi i numeri N + 1 a partire da M + 1.

Un altro modo di vedere questo è considerare l'insieme come un bit impostato. Quindi la procedura di codifica e decodifica è la stessa: capovolgi i bit dal primo fino a ottenere il numero di elementi che desideri nel set.

Ecco un encoder lisp

(defun encode (l)
  (helper 1 1 l nil))

(defun decode (l)
  (helper -1 1 l nil))

(defun helper (cnt cur rem res)
  (cond
   ((= cnt 0)
    (append res rem))
   ((or (null rem) (/= cur (car rem)))
    (helper (- cnt 1) (+ cur 1) rem (append res (list cur))))
   (t
    (helper (+ cnt 1) (+ cur 1) (cdr rem) res))))

e ciò che ottieni quando parti da un insieme di 3 elementi.

(1 2 3) -> (4 5 6 7)
(1 2 4) -> (3 5 6 7)
(1 2 5) -> (3 4 6 7)
(1 2 a) -> (3 4 5 a)
(1 3 4) -> (2 5 6 7)
(1 3 5) -> (2 4 6 7)
(1 3 a) -> (2 4 5 a)
(1 a b) -> (2 3 a b)
(a b c) -> (1 a b c)

Puoi ordinare tutti i 40 set, come:

{1,2,...,40}
{1,2,...,38,39,41}
...
{961,...,1000}

Puoi anche ordinare tutti i 41 set (ce ne sono altri).

Quindi conta l'ordine del tuo 40-set e restituisci il 41-set nella stessa posizione.

(il codice per eseguirlo non è banale da fare, ma non dovrebbe essere molto difficile con alcuni giochi con moltiplicazioni e moduli)

Modifica: questa risposta si basa sull'assunto errato che l'OP volesse che i 40 interi originali fossero inclusi nel set di 41. Come tale, è sbagliato ma lo lascio per ora perché aggiunge una svolta interessante al problema.

Non so se questo è possibile con un set di 40 numeri, ma è possibile aggiungere un numero intero univoco a gruppi di uno o due numeri e rimuoverlo. Ecco la logica di decodifica per questi due casi:

Set di 1: se i numeri nel set codificato sono consecutivi, il numero aggiunto è il numero più grande, altrimenti il numero aggiunto è il più piccolo dei due.

Set di 2: Se due numeri nel set codificato sono separati da uno spazio vuoto di uno o meno, il numero aggiunto è il numero che è non parte di questa coppia, altrimenti il numero aggiunto è quello che cade tra numeri più piccoli e più grandi.

È potrebbe essere in grado di costruire la logica di codifica / decodifica per insiemi di 3, 4, 5 ... 998. È non possibile creare la logica di decodifica per un set di 999. 999 Non funziona perché c'è un solo numero mancante nel suo set e il set codificato riempirà quel numero mancante, risultante in un set contenente ogni numero da 1 a 1000.

Questo è il modo in cui il mio piccolo cervello può sopportarlo. I membri del link potrebbero essere in grado di fornire una dimostrazione e un metodo formali per determinare esattamente quanto può essere grande un set ed essere ancora reversibile per il tuo intervallo da 1 a 1000.

Pensiamo a 4 numeri interi univoci nell'intervallo 1-10. Otteniamo il set di input I = {1, 2, 3, 4} . Dobbiamo produrre un set di output O con |O| = |I| + 1 . La soluzione più banale è restituire il set di input e il più piccolo numero inutilizzato n :

n = min([1, ..., 10] \ I)
O = I u {n}

Questa è ora una mappatura I → O . L'operazione inversa può essere implementata ricordando la coppia (I, O) e guardando l'altra impostata. Non c'è modo di ottenere il set originale senza memorizzare questa connessione!

Se vogliamo avere una mappatura o → i forall o in O with i in I , possiamo mappare ogni numero a se stesso eccetto n che potrebbe mappare al numero più basso in I . Ciò significa che dobbiamo ricordare separatamente n .

Come codice Python:

numbers = range(1, 10+1)
def create_mapping(I):
  for n in numbers:
    if not n in I:
      break
  return (I + [n], n)

def map_back(mapping, x):
  O, n = mapping
  if x == n:
    return min(O)
  if x in O:
    return x
  return None

I = range(1, 5)
mapping = create_mapping(I)
back =  [map_back(mapping, x) for x in range(1, 10+1)]
assert back == [1, 2, 3, 4, 1, None, None, None, None, None]

Inoltre:

O, _ = mapping
assert set(I) == set(map_back(mapping, x) for x in O)

che significa che la mappatura è reversibile

Modifica: questa risposta presuppone che il set di 41 includa il set originale di 40.

Hai davvero due problemi:

Ricerca di un 41 ° numero

Quello che stai cercando qui è un buco in cui puoi introdurre di nascosto un nuovo numero, quindi la prima cosa che devi fare è ordinarla.

Con la tua lista ordinata in mano, le scorciatoie facili sono per vedere se c'è una lacuna all'inizio (il primo numero è maggiore di 1) o la fine (l'ultimo numero è inferiore a 1.000). Se uno di questi è vero, il 41esimo elemento può essere 1 o 1.000 a seconda di quale è. Il gioco è fatto.

Se la lista ordinata contiene 1 e 1.000, devi attraversarla finché non trovi due numeri adiacenti che hanno una differenza maggiore di uno. Lo spazio tra questi due numeri rappresenta il divario, e il 41 ° elemento è un numero in tale intervallo. La cosa più semplice da fare sarebbe una maggiore del minore dei due numeri di uno in meno rispetto al maggiore.

Ripristino dei 40 numeri originali

Il problema del tuo amico ha un difetto in quanto non fornisce alcuna informazione su come viene fornito il set originale di 40 numeri (set non ordinato, elenco, ecc.) o come deve essere restituito il set contenente il 41esimo numero.

Se i set forniti e restituiti sono in realtà un elenco ordinato di 40 elementi (ordinati solo, non necessariamente ordinati), il nuovo numero può essere aggiunto come 41 ° elemento e quindi ritagliato successivamente per tornare all'originale.

Se i set non sono ordinati, non c'è modo di capire quale elemento deve essere rimosso per ripristinare l'originale 40. Semplicemente non sai cosa è stato aggiunto.

Potresti pensare che ci sia un modo intelligente di dare il numero che aggiungi un'intelligenza che rivelerà l'identità del numero aggiunto quando ti verrà consegnato un set di 41 in seguito, ma non lo è. Qualcuno che conosce il tuo algoritmo potrebbe costruire un set valido di 40 che risulterà in un set di 41 che produce la risposta sbagliata quando riduci a 40.