CODEWITHSUNDEEP
algorithm
Rckt
Rckt

Reputation: 185

Calculating unique value from given numbers

Let's say I have some 6 random numbers and I want to calculate some unique value from these numbers.

Edit: Allowed operations are +, -, *, and /. Every number could be used only once. You dont have to use all numbers.

Example: 

Given numbers: 3, 6, 100, 50, 25, 75
Requested result: 953

3 + 6 = 9
9 * 100 = 900
900 + 50 = 950
75 / 25 = 3
3 + 950 = 953

What could be easiest algorithmic approach to write a program that solves this problem?

Upvotes: 3

Views: 199

Answers (5)

Hot Licks
Hot Licks

Reputation: 47739

If you want to guarantee that you generate a unique number from those numbers, with no chance of getting the same number from a different set of numbers, then you should use radix arithmetic, similar to decimal, hex, etc.

But you need to know the max values of the numbers.

Basically, it would be A + B * MAX_A + C * MAX_A * MAX_B + D * MAX_A * MAX_B * MAX_C + E * MAX_A * MAX_B * MAX_C * MAX_D + F * MAX_A * ... * MAX_E

Upvotes: 1

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726849

The easiest approach is to try them all: you have six numbers, meaning that there are up to five spots where you can place an operator, and up to 6! permutations. Given that there are only four operators, you need to go through 6!*4^5, or 737280 possibilities. This can be easily done with a recursive function, or even with nested loops. Depending on the language, you could use a library function to deal with permutations.

A language-agnostic recursive approach would have you define three functions:

int calc(int nums[6], int ops[5], int countNums) {
    // Calculate the results for a given sequence of numbers
    // with the specified operators.
    // nums are your numbers; only countNums need to be used
    // ops are your operators; only countNums-1 need to be used
    // countNums is the number of items to use; it must be from 1 to 6
}

void permutations(int nums[6], int perm[6], int pos) {
    // Produces all permutations of the original numbers
    // nums are the original numbers
    // perm, 0 through pos, is the indexes of nums used in the permutation so far
    // pos, is the number of perm items filled so far
}

void solveRecursive(int numPerm[6], int permLen, int ops[5], int pos) {
    // Tries all combinations of operations on the given permutation.
    // numPermis the permutation of the original numbers
    // permLen is the number of items used in the permutation
    // ops 0 through pos are operators to be placed between elements
    // of the permutation
    // pos is the number of operators provided so far.
}

Upvotes: 4

songlj
songlj

Reputation: 927

use recursion to permutate the numbers and operators. it's O(6!*4^5)

Upvotes: 0

Ted Hopp
Ted Hopp

Reputation: 234847

The easiest algorithmic approach would, I think, be backtracking. It's fairly easy to implement and will always find a solution if one exists. The basic idea is recursive: make an arbitrary choice at each step of building a solution and proceed from there. If it doesn't work out, try a different choice. When you run out of choices, report failure to the previous choice point (or report failure to find a solution if there is no previous choice point).

Your choices are: how many numbers will be involved, what each number is (a choice each number position), and how they are connected by operators (a choice for each operator position).

Upvotes: 4

gnlogic
gnlogic

Reputation: 1034

When you mention "unique numbers", assuming that you mean a result in the possible universe of results generated using all the numbers at hand.

If so, why not try a permutation of all operators and available numbers for a start?

Upvotes: 1

Related Questions