EN VI

PHP: Getting unique combinations of numbers from an array?

How to PHP: Getting unique combinations of numbers from an array

I'm trying to create a lists of possible combination for multiplication of 4 randomly selected numbers from an array of prime numbers to no avail. Any pointers?

Its quite a direct approach and i feel there's something i carelessly missed. here's what i've been stucked with:

//Pruning outcome from controlled lists of Prime Numbers
$primes = array(2, 3, 5, 7, 11, 13, 17, 19, 21);

function getUniqueRandomProductsWithNumbers($arr, $n) {
  $seen = array(); // Store seen combinations to avoid duplicates
  $productsWithNumbers = array();

  while (count($productsWithNumbers) < pow(count($arr), $n)) {
    $selected = array_rand($arr, $n); // Get random indexes
    sort($selected); // Sort to ensure order for checking duplicates
    $key = implode(",", $selected); // Create a unique key based on sorted indexes

    if (!isset($seen[$key])) {
      $product = 1;
      $numbers = array();
      foreach ($selected as $i) {
        $product *= $arr[$i];
        $numbers[] = $arr[$i];
      }
      $seen[$key] = true;
      $productsWithNumbers[] = array($numbers, $product);
    }
  }

  return $productsWithNumbers;
}

$uniqueProducts = getUniqueRandomProductsWithNumbers($primes, 4);
echo "Unique Products with Numbers:\n";
foreach ($uniqueProducts as $productSet) {
  echo "Numbers: ";
  print_r($productSet[0]); // Print the numbers array
  echo ", Product: " . $productSet[1] . "\n";
}

Really appreciate any pointers. Thanx in advance...

Solution:

It seems like you're on the right track! However, there are a couple of things that need to be adjusted to ensure the code works correctly:

Array of Prime Numbers:
- In your $primes array, the number 21 should not be included because 21 is not a prime number. Replace it with the prime number 23.
Loop Condition:
- Your current loop condition count($productsWithNumbers) < pow(count($arr), $n) is not optimal. This condition might not always work as expected, especially when dealing with duplicates. It's better to check against the total number of unique combinations possible, which is nCr, where n is the total number of elements in $arr and r is the number of elements you're choosing. For this case, it's nCr(9, 4).
Unique Key for Duplicates:
- The way you are creating the unique key to check for duplicates is not handling permutations correctly. When you sort the selected indexes, it will not prevent duplicates because different orders will still create the same sorted key. Instead, you can directly use the sorted values themselves to check for uniqueness.

Here's the modified code:

// Pruning outcome from controlled lists of Prime Numbers
$primes = array(2, 3, 5, 7, 11, 13, 17, 19, 23); // Changed 21 to 23

function nCr($n, $r) {
  return factorial($n) / (factorial($r) * factorial($n - $r));
}

function factorial($n) {
  if ($n <= 1) {
    return 1;
  } else {
    return $n * factorial($n - 1);
  }
}

function getUniqueRandomProductsWithNumbers($arr, $n) {
  $totalCombinations = nCr(count($arr), $n);
  $productsWithNumbers = array();

  while (count($productsWithNumbers) < $totalCombinations) {
    $selected = array_rand($arr, $n); // Get random indexes
    sort($selected); // Sort to ensure order for checking duplicates
    $numbers = array_map(function ($i) use ($arr) {
      return $arr[$i];
    }, $selected);

    $product = array_product($numbers);

    if (!in_array($product, $productsWithNumbers)) {
      $productsWithNumbers[] = $product;
      echo "Numbers: ";
      print_r($numbers);
      echo ", Product: " . $product . "\n";
    }
  }

  return $productsWithNumbers;
}

$uniqueProducts = getUniqueRandomProductsWithNumbers($primes, 4);

In this updated code:

I've added a nCr function to calculate the total number of combinations.
Changed the loop condition to count($productsWithNumbers) < $totalCombinations.
Removed the $seen array and directly checked if the product is already in $productsWithNumbers.
Removed the unnecessary $key variable.

This should now generate unique combinations of 4 prime numbers and their products without duplicates.