Task — Unequal triplets

You are given an array of positive integers. Write a script to find the number of triplets (i, j, k) that satisfies num[i] != num[j], num[j] != num[k] and num[k] != num[i].

Examples

Example 1
Input: @ints = (4, 4, 2, 4, 3)
Output: 3

(0, 2, 4) because 4 != 2 != 3
(1, 2, 4) because 4 != 2 != 3
(2, 3, 4) because 2 != 4 != 3

Example 2
Input: @ints = (1, 1, 1, 1, 1)
Output: 0

Example 3
Input: @ints = (4, 7, 1, 10, 7, 4, 1, 1)
Output: 28

triplets of 1, 4, 7  = 3x2×2 = 12 combinations
triplets of 1, 4, 10 = 3×2×1 = 6  combinations
triplets of 4, 7, 10 = 2×2×1 = 4  combinations
triplets of 1, 7, 10 = 3x2x1 = 6 combinations

Analysis

The requirement is that the three members of the triplet must all have different values, but if a number is repeated in @ints, then the separate instances may form separate triplets. For example, (1, 1, 2, 3) can form two triplets, (1, 2, 3) and (1, 2, 3). The ordering within the triplet is not significant, so for example (1, 2, 3) and (2, 1, 3) are considered the same triplet.

I therefore chose - as Mohammad has done in the examples - to show the members of each triplet in increasing order, knowing that any other order would merely duplicate one I had already.

My solutions starts with sorting @ints in ascending numerical order.

I then loop over @ints, building:

• an array @unique of unique values, and
• an array @count of the number of occurrences of these values.

Now I use three nested loops to find every qualifying triplet. As the values are in increasing order, I only need to iterate:

• the first index from 0 to third last position,
• the third index from 2 to the last position, and
• the second index from the first index plus one to the third index minus one.

For each triplet this creates I need to add into the total the product of the three corresponding @count values. So using example 3 above, there are three 1s, so every triplet involving 1 happens 3 times and so on.

Try it 

Try running the script with any input, for example:
4, 4, 2, 4, 3

Your @ints =

⤡

#!/usr/bin/perl

use v5.16;    # The Weekly Challenge - 2023-09-11
use utf8;     # Week 234 task 2 - Unequal triplets
use strict;   # Peter Campbell Smith
use warnings; # Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

my ($j, @ints);
unequal_triplets(4, 4, 4, 2, 3);
unequal_triplets(1, 1, 1, 1, 1);
unequal_triplets(4, 7, 1, 10, 7, 4, 1, 1);
unequal_triplets(-1, 0, 1);
unequal_triplets(5, 4, 3);

# bigger one
for $j (1 .. 9) {
    push @ints, int(rand(6));
}
unequal_triplets(@ints);

sub unequal_triplets {
    
    my (@ints, $n, $j, $int, @count, @unique, $item1, $item2, $item3, $combs, $i, $explain, $total, $u);
    
    # sanity check
    @ints = sort {$a <=> $b} @_;
    $n = scalar @ints;
    return unless $n >= 3;
    
    # get unique values and count of each value
    $j = -1;
    for $i (0 .. $n - 1) {
        $j ++ if ($i == 0 or $ints[$i] != $unique[$j]);
        $unique[$j] = $ints[$i];
        $count[$j] ++;
    }
    
    # get combinations
    $u = scalar @unique;
    $total = 0;
    $explain = '';
    for $item1 (0 .. $u - 3) {
        for $item3 (2 .. $u - 1) {
            for $item2 ($item1 + 1 .. $item3 - 1) {
                $combs = $count[$item1] * $count[$item2] * $count[$item3];
                $total += $combs;
                $explain .= qq[\n   triplet $unique[$item1], $unique[$item2], $unique[$item3] => ] .
                    qq[$count[$item1] * $count[$item2] * $count[$item3] = $combs];
            }
        }
    }
    
    say qq[\nInput:  \@ints = (] . join(', ', @_) . ')';
    say qq[Output: $total$explain];
}

Output

Input:  @ints = (4, 4, 4, 2, 3)
Output: 3
   triplet 2, 3, 4 => 1 * 1 * 3 = 3

Input:  @ints = (1, 1, 1, 1, 1)
Output: 0

Input:  @ints = (4, 7, 1, 10, 7, 4, 1, 1)
Output: 28
   triplet 1, 4, 7 => 3 * 2 * 2 = 12
   triplet 1, 4, 10 => 3 * 2 * 1 = 6
   triplet 1, 7, 10 => 3 * 2 * 1 = 6
   triplet 4, 7, 10 => 2 * 2 * 1 = 4

Input:  @ints = (-1, 0, 1)
Output: 1
   triplet -1, 0, 1 => 1 * 1 * 1 = 1

Input:  @ints = (5, 4, 3)
Output: 1
   triplet 3, 4, 5 => 1 * 1 * 1 = 1

Input:  @ints = (0, 3, 3, 1, 2, 3, 0, 5, 3)
Output: 43
   triplet 0, 1, 2 => 2 * 1 * 1 = 2
   triplet 0, 1, 3 => 2 * 1 * 4 = 8
   triplet 0, 2, 3 => 2 * 1 * 4 = 8
   triplet 0, 1, 5 => 2 * 1 * 1 = 2
   triplet 0, 2, 5 => 2 * 1 * 1 = 2
   triplet 0, 3, 5 => 2 * 4 * 1 = 8
   triplet 1, 2, 3 => 1 * 1 * 4 = 4
   triplet 1, 2, 5 => 1 * 1 * 1 = 1
   triplet 1, 3, 5 => 1 * 4 * 1 = 4
   triplet 2, 3, 5 => 1 * 4 * 1 = 4