-3

I need an algorithm to find the count of unique tuples of three numbers from an array of positive integers where the three numbers can be picked consecutively or randomly but following the same array order while picking.

For example consider an array [1, 4, 1, 1, 1, 2]

All the unique tuples of three numbers are:

[1, 4, 1]

[1, 4, 2]

[1, 1, 1]

[1, 1, 2]

[4, 1, 1]

[4, 1, 2]

So the answer is 6.

I need an algorithm to solve this.

Bhargav Nanekalva
  • 606
  • 9
  • 31

3 Answers3

1

Solution for the new question. This is called complete search algorithm. Complexity is O(n^3 log (n)).

int n;
cin >> n;

vi a(n);

for(int i = 0; i < n; i++) cin >> a[i];

int last1 = INF, last2 = INF, last3 = INF;
int count = 0;
set <int> s1;
set <pair<int, int>> s2;
set <tuple <int, int, int> > s3;
for(int i = 0; i < n; i++) {
    if(s1.count(a[i])) continue;
    s1.insert(a[i]);
    for(int j = i + 1; j < n; j++) {
        if(s2.count({a[i], a[j]})) continue;
        s2.insert({a[i], a[j]});
        for(int k = j + 1; k < n; k++) {
            if(s3.count({a[i], a[j], a[k]})) continue;
            s3.insert({a[i], a[j], a[k]});
            count++;
            cout << a[i] << " " << a[j] << " " << a[k] << "\n";
            last3 = a[k];
        }
        last2 = a[j];
    }
    last1 = a[i];
}

cout << count << "\n";
satvik choudhary
  • 124
  • 2
  • 9
  • https://ideone.com/mk78Zf Full c++ code. Though I am using c++ std::set. You can also use std::unordered_set which is equivalent to hashing and will be easier to understand if for some reason you want the whole algorithm. – satvik choudhary Jun 12 '18 at 12:52
1

Is this what you are looking for?

int n;
cin >> n;

vi a(n);

for(int i = 0; i < n; i++) {
    cin >> a[i];
}

set <tuple<int, int, int> > set1;

for(int i = 0; i < n - 2; i++) {
    tuple <int, int, int> c = {a[i], a[i + 1], a[i + 2]};
    if(!set1.count(c)) set1.insert(c);
}
cout << set1.size() << "\n";
for(auto el: set1) {
    cout << get<0> (el) << " " << get<1> (el) << " " << get <2> (el) << "\n";
}
satvik choudhary
  • 124
  • 2
  • 9
  • Thanks Satvik! How do I run this on a mac? Also please tell me your algorithm, that is all I actually need. – Bhargav Nanekalva Jun 11 '18 at 11:48
  • This is in C++. The algorithm is complete search with a special data structure called Red Black tree which is by default implemented in most languages. Here it is used as set. Complete code https://ideone.com/LYJ0kN – satvik choudhary Jun 12 '18 at 12:42
  • For mac create a .cpp file for the code on ideone and see this https://stackoverflow.com/questions/221185/how-to-compile-and-run-c-c-in-a-unix-console-mac-terminal – satvik choudhary Jun 12 '18 at 12:45
  • I also think my code works only for the original question which allowed only consecutive. – satvik choudhary Jun 12 '18 at 12:47
0

I have an algorithm whose usability will depend on the language that you are using.

I am writing my answer in reference to C++. So if the entries of the array is strictly less than 1,000,000 then you can use my idea.So here it goes:

The basic idea is to store the tuple of 3 numbers(say a,b and c in order) as k=10^12*a+10^6*b+c.

So every unique k will be a unique tuple which you can get by

a = k/10^12

b = (k/10^6)%10^6

c = k%10^6

So for example a=123 ,b=58469 and c=12 then k = 123058469000012

and a,b,c can be recovered as k/10^12 = 123,(k/10^6)%10^6=058469 and k%10^6=000012

For getting k you can iterate the array in three nested loops.

For counting unique k's you can use any data structures like map,set etc. depending on your programming language.

If elements are larger you can simply iterate through the array in three nested loops and store the numbers in say std::pair< long long , pair < long long ,long long > > (a data structure in C++) and then you can use again data structures like set,map etc. to count unique pairs.

P.S. : I didn't write code because there was no language specified but hope my idea helps.

Chaman Agrawal
  • 86
  • 2
  • 11