Déterminer le nombre manquant dans le flux de données

Question

Nous recevons un flux de $ n-1 $ par paire de numéros différents de l'ensemble $ \ left \ {1, \ points, n \ right \} $.

Comment puis-je déterminer le nombre manquant avec un algorithme qui lit le flux une fois et utilise une mémoire de seulement $ O (\ n log_2) $ les bits?

Answer 1

Vous savez $ \ sum_ {i = 1} ^ ni = \ frac {n (n + 1)} {2} $, et parce que $ S = \ frac {n (n + 1)} {2} $ pourrait être codé en $ O (\ log (n)) $ bits de ce qui peut être fait en $ O (\ log n) $ mémoire et dans un chemin (trouver juste $ S - \ mathrm {currentSum} $, c'est le numéro manquant ).

Mais ce problème pourrait être résolu en cas général (pour $ k $ de constante): nous avons k $ numéros manquants $, savoir tous. Dans ce cas, au lieu de calculer juste somme de $ y_i $, somme calculate de puissance j'st de x_i $ $ pour tous $ 1 \ le j \ le k $ (je supposais x_i $ est le nombre manquant et $ y_i $ est un nombre d'entrée ):

$ \ qquad \ displaystyle \ begin {align}   \ {Sum_ i = 1} ^ k = x_i & S_1, \\   \ {Sum_ i = 1} ^ k x_i ^ 2 = & S_2, \\     & \ Vdots \\  \ {Sum_ i = 1} ^ k x_i ^ k = & S_k \ End {align} $ $ \ qquad (1) $

Rappelez-vous que vous pouvez calculer S_1 $, ... S_k $ tout simplement, parce que $ S_1 = S - \ somme y_i $, S_2 $ = \ sum i ^ 2 - \ somme y_i ^ 2 $, ...

Maintenant, pour trouver des numéros manquants, vous devez résoudre $ (1) $ pour trouver tous x_i $ $.

Vous pouvez calculer:

$ = P 1 \ somme x_i $, $ = P_2 \ somme x_i \ cdot x_j $, ..., $ = p_k \ prod x_i $ (2) $.

Pour cette rappelez-vous que $ = P 1 S_1 $, $ = P_2 \ frac {S_1 ^ 2 - S_2 } {2} $, ...

$ P_i $ est de $ coefficients P = (x-x 1) \ cdot (x-x 2) \ cdots (x-x_k) $, mais $ P $ pourrait être pris unique, de sorte que vous pouvez trouver les numéros manquants.

Ce ne sont pas mes pensées; lire cette .

Answer 2

Dans le commentaire ci-dessus:

Avant de traiter le flux, allouer $ \ lceil \ log_2 n \ rceil $ bits, dans lequel vous écrivez $ x: = \ bigoplus_ {i = 1} ^ n \ mathrm {bin} (i) $ ($ \ mathrm {bin} (i) $ est la représentation binaire de $ i $ et $ \ oplus $ est exclusif ou pointwise). Naïvement, cela prend $ \ mathcal {O} (n) $ temps.

Lors du traitement du flux, quand on lit un numéro $ j $, $ x calculer: = x \ oplus \ mathrm {bin} (j) $. Soit $ k $ soit le numéro unique de $ \ {1, ... n \} $ qui ne sont pas inclus dans le flux. Après avoir lu tout le courant, nous avons $$ x = \ left (\ bigoplus_ {i = 1} ^ n \ mathrm {bin} (i) \ right) \ oplus \ left (\ bigoplus_ {i \ neq k} \ mathrm {bin} (i) \ right ) = \ Mathrm {bin} (k) \ oplus \ bigoplus_ {i \ NEQ k} (\ mathrm {bin} (i) \ oplus \ mathrm {bin} (i)) = \ mathrm {bin} (k), $ $ ce qui donne le résultat souhaité.

Par conséquent, nous avons utilisé $ \ mathcal {O} (\ log n) $ l'espace, et ont un temps d'exécution global de $ \ mathcal {O} (n) $.

Answer 3

La solution de HdM fonctionne. Je codé en C ++ pour le tester. Je ne peux pas limiter le value à $ O (\ n log_2) $ bits mais je suis sûr que vous pouvez facilement montrer comment seulement que le nombre de bits est en fait défini.

Pour ceux qui veulent un code pseudo, en utilisant un simple $ \ texte {pli} $ avec l'opération exclusive ou ($ \ oplus $):

$$ \ texte {manquant} = \ texte {plier} (\ oplus, \ {1, \ ldots, N \} \ cup \ texte {InputStream}) $$

la preuve à la main wavey: A $ \ oplus $ ne demande jamais plus de bits que son entrée, il en résulte que aucun résultat intermédiaire dans la demande ci-dessus plus que les bits maximum de l'entrée (donc $ O (\ log_2 n) $ morceaux). $ \ Oplus $ est commutative, et $ x \ oplus x = 0 $, donc si vous développez ci-dessus et une paire de toutes les données présentes dans le flux que vous serez à gauche que d'une seule valeur non apparié, le nombre manquant.

#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>

using namespace std;

void find_missing( int const * stream, int len );

int main( int argc, char ** argv )
{
    if( argc < 2 )
    {
        cerr << "Syntax: " << argv[0] << " N" << endl;
        return 1;
    }
    int n = atoi( argv[1] );

    //construct sequence
    vector<int> seq;
    for( int i=1; i <= n; ++i )
        seq.push_back( i );

    //remove a number and remember it
    srand( unsigned(time(0)) );
    int remove = (rand() % n) + 1;
    seq.erase( seq.begin() + (remove - 1) );
    cout << "Removed: " << remove << endl;

    //give the stream a random order
    std::random_shuffle( seq.begin(), seq.end() );

    find_missing( &seq[0], int(seq.size()) );
}

//HdM's solution
void find_missing( int const * stream, int len )
{
    //create initial value of n sequence xor'ed (n == len+1)
    int value = 0;
    for( int i=0; i < (len+1); ++i )
        value = value ^ (i+1);

    //xor all items in stream
    for( int i=0; i < len; ++i, ++stream )
        value = value ^ *stream;

    //what's left is the missing number
    cout << "Found: " << value << endl;
}