How to find a number from its 3 digit combinations?

Question

If there is a 8 digit number 65478209 (the digits in the number can repeat) and given the combinations are always in the order of the number, then if all combinations 8c3 = 56 combinations are given then what will be the shortest solution to find out the number(s) ?

An example scenario could be a bank login where user need to enter 3 random digits of their code like 3rd, 5th and 6th, where this is one of the 8c3 combination. So if all 8c3 combinations are given then what will be the solution/logic to find the number? (or first number if there are more numbers as a solution)

For problem solving in programming language, the input will an array of 56 3 digit combinations, and we have to find the code which is "65478209" or whatever.

This is actually really interesting. It's kind of like a Sudoku solver. My first thought without coding anything is to make a bunch of arrays. Do you know that digits will not be repeated? non-repeating digits makes it a lot easier. — goodguy5
@goodguy5, yes the digits can be repeated. Its alot interesting to solve this, but I am not sure how to target the community and couldnt find solutions online. Would be good if you guys could pop in input — stak

Hexoul Hexoul · Accepted Answer · 2016-03-09T11:23:24

How about using permutation? I write the simple code in c++ style. Check it.

int k = 3;
string digit = "65478209";
int digitLen = digit.length();

int* indexArr = new int[digitLen];
for(int i=0; i < digitLen; i++) indexArr[i] = i;

do
{
    bool isInOrder=true;
    string ret = "";
    for(int i=1; i < k; i++) if(indexArr[i] < indexArr[i-1])
    {
        isInOrder = false;
        break;
    }
    if(!(isInOrder)) continue;

    for(int i=0; i < k; i++) ret += digit[indexArr[i]];
} while(next_permutation(indexArr, indexArr+digitLen));

delete indexArr;

Edit

here is my solution.

vector<string> combinations;
set<int> includedDigit;
vector<int> referCnt;

// Get reference count from all precedences
for(int i=0; i < combinations.size(); i++)
{
    string e = combinations[i];
    for(int j=0; j < k-1; j++)
    {
        includedDigit.insert(e.at(j) - '0');
        for(int l=j+1; l < k; l++)
        {
            int curDigit = e.at(l) - '0';
            referCnt.push_back(curDigit);
        }
    }
}

// Sorting reference counts with digit
vector<pair<int,int>> ret;
for(int i=0; i < 10; i++)
{
    int digitCnt = count(referCnt.begin(), referCnt.end(), i);
    if(digitCnt == 0 && includedDigit.find(i) != includedDigit.end()) ret.push_back(make_pair(1, i));
    else if(digitCnt != 0) ret.push_back(make_pair(digitCnt, i));
}
sort(ret.begin(), ret.end());

// Print the result
for(auto it=ret.begin(); it != ret.end(); it++)
{
    pair<int,int> val = *it;
    cout << val.second;
}

It works although I think it can be shorten. In addition, if original digit is not kind of permutation, it should be more complex.

How to find a number from its 3 digit combinations?

2 Answers

Edit