How to get all possible combinations from two arrays in Java?
I have the two arrays:
String operators = {"+", "-", "*"};
int numbers = {48, 24, 12, 6};
And I want to get all possible combination in a String format like this:
48+24+12+6
48+24+12-6
48+24+12*6
48+24-12+6
48+24-12-6
48+24-12*6
..........
48*24*12*6
This what I have tried:
for(int i = 0; i < operators.length; i++) {
System.out.println(numbers[0] + operators[i] + numbers[1] + operators[i] + numbers[2] + operators[i] + numbers[3]);
}
But it only prints:
48+24+12+6
48-24-12-6
48*24*12*6
How to solve this?
This is not a duplicate because I don't want to get every two pairs of data, I want to get every combination in 4 pairs. The duplicate is different.
java arrays algorithm
add a comment |
I have the two arrays:
String operators = {"+", "-", "*"};
int numbers = {48, 24, 12, 6};
And I want to get all possible combination in a String format like this:
48+24+12+6
48+24+12-6
48+24+12*6
48+24-12+6
48+24-12-6
48+24-12*6
..........
48*24*12*6
This what I have tried:
for(int i = 0; i < operators.length; i++) {
System.out.println(numbers[0] + operators[i] + numbers[1] + operators[i] + numbers[2] + operators[i] + numbers[3]);
}
But it only prints:
48+24+12+6
48-24-12-6
48*24*12*6
How to solve this?
This is not a duplicate because I don't want to get every two pairs of data, I want to get every combination in 4 pairs. The duplicate is different.
java arrays algorithm
So the operators is limited, only 3?
– ZhaoGang
Dec 14 at 13:54
@ZhaoGang Yes, I have only 3 operators.
– Oleg Caralanski
Dec 14 at 13:58
add a comment |
I have the two arrays:
String operators = {"+", "-", "*"};
int numbers = {48, 24, 12, 6};
And I want to get all possible combination in a String format like this:
48+24+12+6
48+24+12-6
48+24+12*6
48+24-12+6
48+24-12-6
48+24-12*6
..........
48*24*12*6
This what I have tried:
for(int i = 0; i < operators.length; i++) {
System.out.println(numbers[0] + operators[i] + numbers[1] + operators[i] + numbers[2] + operators[i] + numbers[3]);
}
But it only prints:
48+24+12+6
48-24-12-6
48*24*12*6
How to solve this?
This is not a duplicate because I don't want to get every two pairs of data, I want to get every combination in 4 pairs. The duplicate is different.
java arrays algorithm
I have the two arrays:
String operators = {"+", "-", "*"};
int numbers = {48, 24, 12, 6};
And I want to get all possible combination in a String format like this:
48+24+12+6
48+24+12-6
48+24+12*6
48+24-12+6
48+24-12-6
48+24-12*6
..........
48*24*12*6
This what I have tried:
for(int i = 0; i < operators.length; i++) {
System.out.println(numbers[0] + operators[i] + numbers[1] + operators[i] + numbers[2] + operators[i] + numbers[3]);
}
But it only prints:
48+24+12+6
48-24-12-6
48*24*12*6
How to solve this?
This is not a duplicate because I don't want to get every two pairs of data, I want to get every combination in 4 pairs. The duplicate is different.
java arrays algorithm
java arrays algorithm
edited Dec 14 at 14:03
PradyumanDixit
2,9462819
2,9462819
asked Dec 14 at 13:46
Oleg Caralanski
956
956
So the operators is limited, only 3?
– ZhaoGang
Dec 14 at 13:54
@ZhaoGang Yes, I have only 3 operators.
– Oleg Caralanski
Dec 14 at 13:58
add a comment |
So the operators is limited, only 3?
– ZhaoGang
Dec 14 at 13:54
@ZhaoGang Yes, I have only 3 operators.
– Oleg Caralanski
Dec 14 at 13:58
So the operators is limited, only 3?
– ZhaoGang
Dec 14 at 13:54
So the operators is limited, only 3?
– ZhaoGang
Dec 14 at 13:54
@ZhaoGang Yes, I have only 3 operators.
– Oleg Caralanski
Dec 14 at 13:58
@ZhaoGang Yes, I have only 3 operators.
– Oleg Caralanski
Dec 14 at 13:58
add a comment |
8 Answers
8
active
oldest
votes
Use a triple loop:
for (int i=0; i < operators.length; ++i) {
for (int j=0; j < operators.length; ++j) {
for (int k=0; k < operators.length; ++k) {
System.out.println(numbers[0] + operators[i] + numbers[1] + operators[j] +
numbers[2] + operators[k] + numbers[3]);
}
}
}
You essentially want to take the cross product of the operators vector (if it were a vector). In Java, this translates to a triply-nested set of loops.
What shall we do if we have many operators , much more than 3
– ZhaoGang
Dec 14 at 13:54
10
This doesn't scale properly with number of operators.
– SomeDude
Dec 14 at 13:54
Then we need a backtrack, but it depends on the requirement
– ZhaoGang
Dec 14 at 13:55
I only have three operators. This is what I was looking for. Saved my day!!! Thanks you so much Tim!!
– Oleg Caralanski
Dec 14 at 13:57
2
You refer to a mathematical equation/operation that can be used to solve this problem. Would you be able to elaborate on that, or at least show the equation explicitly?
– MindS1
Dec 14 at 15:03
|
show 3 more comments
While @TimBiegeleisen solution would work like a charm, its complexity might be an issue. The better approach would be a code like this:
static void combinationUtil(int arr, int n, int r, int index, int data, int i)
{
// Current combination is ready to be printed, print it
if (index == r)
{
for (int j=0; j<r; j++)
System.out.print(data[j]+" ");
System.out.println("");
return;
}
// When no more elements are there to put in data
if (i >= n)
return;
// current is included, put next at next location
data[index] = arr[i];
combinationUtil(arr, n, r, index+1, data, i+1);
// current is excluded, replace it with next (Note that
// i+1 is passed, but index is not changed)
combinationUtil(arr, n, r, index, data, i+1);
}
// The main function that prints all combinations of size r
// in arr of size n. This function mainly uses combinationUtil()
static void printCombination(int arr, int n, int r)
{
// A temporary array to store all combination one by one
int data=new int[r];
// Print all combination using temprary array 'data'
combinationUtil(arr, n, r, 0, data, 0);
}
Source: GeeksForGeeks and my IDE :)
Thanks PradyumanDixit I'll go with @TimBiegeleisen solution. Voted up through.
– Oleg Caralanski
Dec 14 at 14:06
2
Worth pointing out that recursion has its own problems: too many iterations and you'll get a StackOverflowException
– David Lavender
Dec 14 at 14:25
2
Small addition, but prefer writing the array brackets before the name and after the type:int data
and not C styleint data
– Lino
Dec 14 at 14:37
@DavidLavender, yes, but, with recursion in this code, I don't think there would be problems upto fairly big numbers.
– PradyumanDixit
Dec 14 at 14:48
@DavidLavender If the array were long enough to overflow the stack, the output would be too big to fit in this universe.
– Solomonoff's Secret
Dec 14 at 18:14
add a comment |
This sounds like a textbook case for a recursive solution:
public static void combineAndPrint(String pieces, String operators) {
if (pieces.length < 1) {
// no pieces? do nothing!
} else if (pieces.length == 1) {
// just one piece? no need to join anything, just print it!
System.out.println(pieces[0]);
} else {
// make a new array that's one piece shorter
String newPieces = new String[pieces.length - 1];
// copy all but the first two pieces into it
for (int i = 2; i < pieces.length; i++) {
newPieces[i - 1] = pieces[i];
}
// combine the first two pieces and recurse
for (int i = 0; i < operators.length; i++) {
newPieces[0] = pieces[0] + operators[i] + pieces[1];
combineAndPrint(newPieces, operators);
}
}
}
public static void main(String args) {
String operators = {"+", "-", "*"};
String numbers = {"48", "24", "12", "6"};
combineAndPrint(numbers, operators);
}
Try it online!
BTW, to generalize this method so that you can do more things with the generated expressions than just printing them, I would recommend making it accept an extra Consumer<String>
parameter. That is, you could rewrite the method declaration as:
public static void combine(String pieces, String operators, Consumer<String> consumer) {
and replace the System.out.println(pieces[0])
with consumer.accept(pieces[0])
and the recursive call to combineAndPrint(newPieces, operators)
with combine(newPieces, operators, consumer)
. Then just call it from your main method e.g. as:
combine(numbers, operators, s -> System.out.println(s));
Try it online!
(Of course, doing it in this more flexible way requires a somewhat modern Java version — Java 8 or later, to be specific — whereas the first example I showed above should work on even ancient versions all the way down to Java 1.0. Maybe in some future version of Java we'll get proper support for coroutines and generators, like Python and Kotlin and even modern JS already have, and then we won't even need to pass the consumer around any more.)
This should be accepted.
– Eric Wang
Dec 14 at 20:18
It also worked. Thanks you! Voted-up. Thank you Ilmari!
– Oleg Caralanski
Dec 15 at 7:43
@IlmariKaronen Isn't more correct to iterate starting from 1 and not from 2?for (int i = 1; i < pieces.length; i++)
– Oleg Caralanski
Dec 17 at 9:42
@OlegCaralanski: We want to copy all but the first two elements ofpieces
intonewPieces
, leaving the first slot ofnewPieces
free for the combination of the first two elements ofpieces
. We can do this with eitherfor (int i = 2; i < pieces.length; i++) newPieces[i - 1] = pieces[i];
orfor (int i = 1; i < newPieces.length; i++) newPieces[i] = pieces[i + 1];
. Either way works. (Of course, it also wouldn't break anything if we started either loop one element earlier, but then we'd be doing useless work by copyingpieces[1]
intonewPieces[0]
only for it to be overwritten below.)
– Ilmari Karonen
Dec 17 at 14:20
add a comment |
I made an alternative, overengineered (but flexible!) "business" solution. The array lengths and values (numbers
and operators
) can be flexible.
package test1;
import java.io.IOException;
import java.util.ArrayList;
public class MainClass
{
public static void main(String args) throws IOException
{
String operators = {"+", "-", "*"};
int numbers = {48, 24, 12, 6};
ArrayList<String> strings = new MainClass().getAllPossibleCombinations(numbers, operators);
for (String string : strings)
{
System.out.println(string);
}
}
private ArrayList<String> getAllPossibleCombinations(int numbers, String operators)
{
if (numbers.length < 2) throw new IllegalArgumentException("Length of numbers-array must be at least 2");
if (operators.length < 1) throw new IllegalArgumentException("Length of operators-array must be at least 1");
ArrayList<String> returnList = new ArrayList<>();
int indexes = new int[numbers.length - 1];
while (true)
{
StringBuilder line = new StringBuilder();
for (int i = 0; i < numbers.length; i++)
{
int number = numbers[i];
line.append(number);
if (i < indexes.length)
{
line.append(operators[indexes[i]]);
}
}
returnList.add(line.toString());
try
{
this.updateIndexes(indexes, operators.length - 1);
}
catch (NoMoreCombinationsException e)
{
break;
}
}
return returnList;
}
private void updateIndexes(int currentIndexes, int maxValue) throws NoMoreCombinationsException
{
if (this.intArrayIsOnly(currentIndexes, maxValue))
{
throw new NoMoreCombinationsException();
}
for (int i = currentIndexes.length - 1; i >= 0; i--)
{
int currentIndex = currentIndexes[i];
if (currentIndex < maxValue)
{
currentIndexes[i] = currentIndex + 1;
break;
}
else
{
currentIndexes[i] = 0;
}
}
}
private boolean intArrayIsOnly(int array, int value)
{
for (int iteratedValue : array)
{
if (iteratedValue != value) return false;
}
return true;
}
}
class NoMoreCombinationsException extends Exception
{
public NoMoreCombinationsException()
{
}
public NoMoreCombinationsException(String message)
{
super(message);
}
public NoMoreCombinationsException(String message, Throwable cause)
{
super(message, cause);
}
public NoMoreCombinationsException(Throwable cause)
{
super(cause);
}
public NoMoreCombinationsException(String message, Throwable cause, boolean enableSuppression, boolean writableStackTrace)
{
super(message, cause, enableSuppression, writableStackTrace);
}
}
Works like a charm :)
Kudos for writing clean, executable and self explanatory code :)
– PradyumanDixit
Dec 14 at 14:47
Thank you too Impulse! Voted up through.
– Oleg Caralanski
Dec 14 at 14:54
I wouldn't call it printAllPossible... That method doesn't actually print anything. Maybe generate.
– findusl
Dec 14 at 16:41
2
You can simplify this... Make your methods static and return aboolean
inupdateIndexes
. Avoid using exceptions in flow-control; and, favor the interfaceList
instead of theArrayList
implementation in your APIs.
– Jan Nielsen
Dec 14 at 17:53
add a comment |
As already pointed out by findusl in his answer, the problem here is, strictly speaking, not to find any sort of "combination of two arrays". Instead, you basically just want to find all possible combinations of the available operators.
(The fact that you later want to "interveave" them with operands is rather unrelated to the core of the question)
So here is another option for solving this: You can create an iterable over all combinations of a certain number of elements from a certain set (in your case: the operators) and then simply combine the results with the other set (in your case: the operands).
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
public class OperatorsTest
{
public static void main(String args)
{
String operators = {"+", "-", "*"};
int numbers = {48, 24, 12, 6};
CombinationIterable<String> iterable =
new CombinationIterable<String>(3, Arrays.asList(operators));
for (List<String> element : iterable)
{
System.out.println(interveave(element, numbers));
}
}
private static String interveave(List<String> operators, int numbers)
{
StringBuilder sb = new StringBuilder();
for (int i=0; i<operators.size(); i++)
{
sb.append(numbers[i]);
sb.append(operators.get(i));
}
sb.append(numbers[numbers.length-1]);
return sb.toString();
}
}
class CombinationIterable<T> implements Iterable<List<T>>
{
private final List<T> input;
private final int sampleSize;
private final int numElements;
public CombinationIterable(int sampleSize, List<T> input)
{
this.sampleSize = sampleSize;
this.input = input;
numElements = (int) Math.pow(input.size(), sampleSize);
}
@Override
public Iterator<List<T>> iterator()
{
return new Iterator<List<T>>()
{
private int current = 0;
private final int chosen = new int[sampleSize];
@Override
public boolean hasNext()
{
return current < numElements;
}
@Override
public List<T> next()
{
if (!hasNext())
{
throw new NoSuchElementException("No more elements");
}
List<T> result = new ArrayList<T>(sampleSize);
for (int i = 0; i < sampleSize; i++)
{
result.add(input.get(chosen[i]));
}
increase();
current++;
return result;
}
private void increase()
{
int index = chosen.length - 1;
while (index >= 0)
{
if (chosen[index] < input.size() - 1)
{
chosen[index]++;
return;
}
chosen[index] = 0;
index--;
}
}
};
}
}
The task resembles that of finding a set of operations that can be done with a certain number of operands and operators, and thus, this Q/A may be related. But whether or not things like associativity or commutativity should be considered here was not mentioned in the question.
It also worked. Voted-up! Thank you Marco!
– Oleg Caralanski
Dec 15 at 7:39
add a comment |
A bit of background information why the answers are they way they are. This problem is not really called "all possible combinations" as that is usually the problem where you can represent the elements as bits and switch them to 0 or 1 whether the element is included or not. This has a complexity of 2^N where N is the amount of operators you have. This can be solved easily in a single loop.
However in your case you have the "urn problem with replacement and sequence". The complexity of this is N^n where n is the amount of spots you have to fill with operators. (This is often seen for pincodes where each spots can be 10 values). So because this is of higher complexity than the "all possible combinations" problem you need multiple loops or recursive calls.
So to answer the question, "how to solve this?". You have to solve it with multiple loops or recursion because of the underlying problem's complexity.
add a comment |
You don't need multiple loops or recursion.
Here's an example showcasing a limited number of loops and no recursion at all.
int combine (int values) {
int size = values.length;
int combinations = 1;
for(int i = 0; i < size; i++) {
combinations *= size;
}
// or int combinations = (int)Math.pow(size, size);
int result = new int[combinations][size];
for(int i = 0; i < combinations; i++) {
int index = i;
for(int j = 0; j < size; j++) {
result[i][j] = values[index % size];
index /= size;
}
}
return result;
}
If you use it with three elements, [1, 2, 3]
, as in the code below:
void testCombine() {
int combinations = combine(new int{1, 2, 3});
for(int combination: combinations) {
System.out.println(Arrays.toString(combination));
}
}
You end up with the following result:
[1, 1, 1]
[2, 1, 1]
[3, 1, 1]
[1, 2, 1]
[2, 2, 1]
[3, 2, 1]
[1, 3, 1]
[2, 3, 1]
[3, 3, 1]
[1, 1, 2]
[2, 1, 2]
[3, 1, 2]
[1, 2, 2]
[2, 2, 2]
[3, 2, 2]
[1, 3, 2]
[2, 3, 2]
[3, 3, 2]
[1, 1, 3]
[2, 1, 3]
[3, 1, 3]
[1, 2, 3]
[2, 2, 3]
[3, 2, 3]
[1, 3, 3]
[2, 3, 3]
[3, 3, 3]
add a comment |
I've developed a class that covers this use case and many others. I call it the TallyCounter. Your question would be answered with this class like this:
package app;
import java.util.HashMap;
import java.util.Map;
import app.TallyCounter.Type;
public class App {
public static void main(String args) throws Exception {
Map<Long, String> map = new HashMap<>();
map.put(0l, "+");
map.put(1l, "-");
map.put(2l, "*");
TallyCounter counter = new TallyCounter(3, Type.NORMAL, 2);
do {
System.out.format("48%s24%s12%s6n",
map.get(counter.getArray()[2]),
map.get(counter.getArray()[1]),
map.get(counter.getArray()[0])
);
counter.increment();
} while (!counter.overflowFlag);
}
}
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53780951%2fhow-to-get-all-possible-combinations-from-two-arrays-in-java%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
8 Answers
8
active
oldest
votes
8 Answers
8
active
oldest
votes
active
oldest
votes
active
oldest
votes
Use a triple loop:
for (int i=0; i < operators.length; ++i) {
for (int j=0; j < operators.length; ++j) {
for (int k=0; k < operators.length; ++k) {
System.out.println(numbers[0] + operators[i] + numbers[1] + operators[j] +
numbers[2] + operators[k] + numbers[3]);
}
}
}
You essentially want to take the cross product of the operators vector (if it were a vector). In Java, this translates to a triply-nested set of loops.
What shall we do if we have many operators , much more than 3
– ZhaoGang
Dec 14 at 13:54
10
This doesn't scale properly with number of operators.
– SomeDude
Dec 14 at 13:54
Then we need a backtrack, but it depends on the requirement
– ZhaoGang
Dec 14 at 13:55
I only have three operators. This is what I was looking for. Saved my day!!! Thanks you so much Tim!!
– Oleg Caralanski
Dec 14 at 13:57
2
You refer to a mathematical equation/operation that can be used to solve this problem. Would you be able to elaborate on that, or at least show the equation explicitly?
– MindS1
Dec 14 at 15:03
|
show 3 more comments
Use a triple loop:
for (int i=0; i < operators.length; ++i) {
for (int j=0; j < operators.length; ++j) {
for (int k=0; k < operators.length; ++k) {
System.out.println(numbers[0] + operators[i] + numbers[1] + operators[j] +
numbers[2] + operators[k] + numbers[3]);
}
}
}
You essentially want to take the cross product of the operators vector (if it were a vector). In Java, this translates to a triply-nested set of loops.
What shall we do if we have many operators , much more than 3
– ZhaoGang
Dec 14 at 13:54
10
This doesn't scale properly with number of operators.
– SomeDude
Dec 14 at 13:54
Then we need a backtrack, but it depends on the requirement
– ZhaoGang
Dec 14 at 13:55
I only have three operators. This is what I was looking for. Saved my day!!! Thanks you so much Tim!!
– Oleg Caralanski
Dec 14 at 13:57
2
You refer to a mathematical equation/operation that can be used to solve this problem. Would you be able to elaborate on that, or at least show the equation explicitly?
– MindS1
Dec 14 at 15:03
|
show 3 more comments
Use a triple loop:
for (int i=0; i < operators.length; ++i) {
for (int j=0; j < operators.length; ++j) {
for (int k=0; k < operators.length; ++k) {
System.out.println(numbers[0] + operators[i] + numbers[1] + operators[j] +
numbers[2] + operators[k] + numbers[3]);
}
}
}
You essentially want to take the cross product of the operators vector (if it were a vector). In Java, this translates to a triply-nested set of loops.
Use a triple loop:
for (int i=0; i < operators.length; ++i) {
for (int j=0; j < operators.length; ++j) {
for (int k=0; k < operators.length; ++k) {
System.out.println(numbers[0] + operators[i] + numbers[1] + operators[j] +
numbers[2] + operators[k] + numbers[3]);
}
}
}
You essentially want to take the cross product of the operators vector (if it were a vector). In Java, this translates to a triply-nested set of loops.
answered Dec 14 at 13:51
Tim Biegeleisen
215k1386137
215k1386137
What shall we do if we have many operators , much more than 3
– ZhaoGang
Dec 14 at 13:54
10
This doesn't scale properly with number of operators.
– SomeDude
Dec 14 at 13:54
Then we need a backtrack, but it depends on the requirement
– ZhaoGang
Dec 14 at 13:55
I only have three operators. This is what I was looking for. Saved my day!!! Thanks you so much Tim!!
– Oleg Caralanski
Dec 14 at 13:57
2
You refer to a mathematical equation/operation that can be used to solve this problem. Would you be able to elaborate on that, or at least show the equation explicitly?
– MindS1
Dec 14 at 15:03
|
show 3 more comments
What shall we do if we have many operators , much more than 3
– ZhaoGang
Dec 14 at 13:54
10
This doesn't scale properly with number of operators.
– SomeDude
Dec 14 at 13:54
Then we need a backtrack, but it depends on the requirement
– ZhaoGang
Dec 14 at 13:55
I only have three operators. This is what I was looking for. Saved my day!!! Thanks you so much Tim!!
– Oleg Caralanski
Dec 14 at 13:57
2
You refer to a mathematical equation/operation that can be used to solve this problem. Would you be able to elaborate on that, or at least show the equation explicitly?
– MindS1
Dec 14 at 15:03
What shall we do if we have many operators , much more than 3
– ZhaoGang
Dec 14 at 13:54
What shall we do if we have many operators , much more than 3
– ZhaoGang
Dec 14 at 13:54
10
10
This doesn't scale properly with number of operators.
– SomeDude
Dec 14 at 13:54
This doesn't scale properly with number of operators.
– SomeDude
Dec 14 at 13:54
Then we need a backtrack, but it depends on the requirement
– ZhaoGang
Dec 14 at 13:55
Then we need a backtrack, but it depends on the requirement
– ZhaoGang
Dec 14 at 13:55
I only have three operators. This is what I was looking for. Saved my day!!! Thanks you so much Tim!!
– Oleg Caralanski
Dec 14 at 13:57
I only have three operators. This is what I was looking for. Saved my day!!! Thanks you so much Tim!!
– Oleg Caralanski
Dec 14 at 13:57
2
2
You refer to a mathematical equation/operation that can be used to solve this problem. Would you be able to elaborate on that, or at least show the equation explicitly?
– MindS1
Dec 14 at 15:03
You refer to a mathematical equation/operation that can be used to solve this problem. Would you be able to elaborate on that, or at least show the equation explicitly?
– MindS1
Dec 14 at 15:03
|
show 3 more comments
While @TimBiegeleisen solution would work like a charm, its complexity might be an issue. The better approach would be a code like this:
static void combinationUtil(int arr, int n, int r, int index, int data, int i)
{
// Current combination is ready to be printed, print it
if (index == r)
{
for (int j=0; j<r; j++)
System.out.print(data[j]+" ");
System.out.println("");
return;
}
// When no more elements are there to put in data
if (i >= n)
return;
// current is included, put next at next location
data[index] = arr[i];
combinationUtil(arr, n, r, index+1, data, i+1);
// current is excluded, replace it with next (Note that
// i+1 is passed, but index is not changed)
combinationUtil(arr, n, r, index, data, i+1);
}
// The main function that prints all combinations of size r
// in arr of size n. This function mainly uses combinationUtil()
static void printCombination(int arr, int n, int r)
{
// A temporary array to store all combination one by one
int data=new int[r];
// Print all combination using temprary array 'data'
combinationUtil(arr, n, r, 0, data, 0);
}
Source: GeeksForGeeks and my IDE :)
Thanks PradyumanDixit I'll go with @TimBiegeleisen solution. Voted up through.
– Oleg Caralanski
Dec 14 at 14:06
2
Worth pointing out that recursion has its own problems: too many iterations and you'll get a StackOverflowException
– David Lavender
Dec 14 at 14:25
2
Small addition, but prefer writing the array brackets before the name and after the type:int data
and not C styleint data
– Lino
Dec 14 at 14:37
@DavidLavender, yes, but, with recursion in this code, I don't think there would be problems upto fairly big numbers.
– PradyumanDixit
Dec 14 at 14:48
@DavidLavender If the array were long enough to overflow the stack, the output would be too big to fit in this universe.
– Solomonoff's Secret
Dec 14 at 18:14
add a comment |
While @TimBiegeleisen solution would work like a charm, its complexity might be an issue. The better approach would be a code like this:
static void combinationUtil(int arr, int n, int r, int index, int data, int i)
{
// Current combination is ready to be printed, print it
if (index == r)
{
for (int j=0; j<r; j++)
System.out.print(data[j]+" ");
System.out.println("");
return;
}
// When no more elements are there to put in data
if (i >= n)
return;
// current is included, put next at next location
data[index] = arr[i];
combinationUtil(arr, n, r, index+1, data, i+1);
// current is excluded, replace it with next (Note that
// i+1 is passed, but index is not changed)
combinationUtil(arr, n, r, index, data, i+1);
}
// The main function that prints all combinations of size r
// in arr of size n. This function mainly uses combinationUtil()
static void printCombination(int arr, int n, int r)
{
// A temporary array to store all combination one by one
int data=new int[r];
// Print all combination using temprary array 'data'
combinationUtil(arr, n, r, 0, data, 0);
}
Source: GeeksForGeeks and my IDE :)
Thanks PradyumanDixit I'll go with @TimBiegeleisen solution. Voted up through.
– Oleg Caralanski
Dec 14 at 14:06
2
Worth pointing out that recursion has its own problems: too many iterations and you'll get a StackOverflowException
– David Lavender
Dec 14 at 14:25
2
Small addition, but prefer writing the array brackets before the name and after the type:int data
and not C styleint data
– Lino
Dec 14 at 14:37
@DavidLavender, yes, but, with recursion in this code, I don't think there would be problems upto fairly big numbers.
– PradyumanDixit
Dec 14 at 14:48
@DavidLavender If the array were long enough to overflow the stack, the output would be too big to fit in this universe.
– Solomonoff's Secret
Dec 14 at 18:14
add a comment |
While @TimBiegeleisen solution would work like a charm, its complexity might be an issue. The better approach would be a code like this:
static void combinationUtil(int arr, int n, int r, int index, int data, int i)
{
// Current combination is ready to be printed, print it
if (index == r)
{
for (int j=0; j<r; j++)
System.out.print(data[j]+" ");
System.out.println("");
return;
}
// When no more elements are there to put in data
if (i >= n)
return;
// current is included, put next at next location
data[index] = arr[i];
combinationUtil(arr, n, r, index+1, data, i+1);
// current is excluded, replace it with next (Note that
// i+1 is passed, but index is not changed)
combinationUtil(arr, n, r, index, data, i+1);
}
// The main function that prints all combinations of size r
// in arr of size n. This function mainly uses combinationUtil()
static void printCombination(int arr, int n, int r)
{
// A temporary array to store all combination one by one
int data=new int[r];
// Print all combination using temprary array 'data'
combinationUtil(arr, n, r, 0, data, 0);
}
Source: GeeksForGeeks and my IDE :)
While @TimBiegeleisen solution would work like a charm, its complexity might be an issue. The better approach would be a code like this:
static void combinationUtil(int arr, int n, int r, int index, int data, int i)
{
// Current combination is ready to be printed, print it
if (index == r)
{
for (int j=0; j<r; j++)
System.out.print(data[j]+" ");
System.out.println("");
return;
}
// When no more elements are there to put in data
if (i >= n)
return;
// current is included, put next at next location
data[index] = arr[i];
combinationUtil(arr, n, r, index+1, data, i+1);
// current is excluded, replace it with next (Note that
// i+1 is passed, but index is not changed)
combinationUtil(arr, n, r, index, data, i+1);
}
// The main function that prints all combinations of size r
// in arr of size n. This function mainly uses combinationUtil()
static void printCombination(int arr, int n, int r)
{
// A temporary array to store all combination one by one
int data=new int[r];
// Print all combination using temprary array 'data'
combinationUtil(arr, n, r, 0, data, 0);
}
Source: GeeksForGeeks and my IDE :)
edited Dec 14 at 14:49
answered Dec 14 at 14:00
PradyumanDixit
2,9462819
2,9462819
Thanks PradyumanDixit I'll go with @TimBiegeleisen solution. Voted up through.
– Oleg Caralanski
Dec 14 at 14:06
2
Worth pointing out that recursion has its own problems: too many iterations and you'll get a StackOverflowException
– David Lavender
Dec 14 at 14:25
2
Small addition, but prefer writing the array brackets before the name and after the type:int data
and not C styleint data
– Lino
Dec 14 at 14:37
@DavidLavender, yes, but, with recursion in this code, I don't think there would be problems upto fairly big numbers.
– PradyumanDixit
Dec 14 at 14:48
@DavidLavender If the array were long enough to overflow the stack, the output would be too big to fit in this universe.
– Solomonoff's Secret
Dec 14 at 18:14
add a comment |
Thanks PradyumanDixit I'll go with @TimBiegeleisen solution. Voted up through.
– Oleg Caralanski
Dec 14 at 14:06
2
Worth pointing out that recursion has its own problems: too many iterations and you'll get a StackOverflowException
– David Lavender
Dec 14 at 14:25
2
Small addition, but prefer writing the array brackets before the name and after the type:int data
and not C styleint data
– Lino
Dec 14 at 14:37
@DavidLavender, yes, but, with recursion in this code, I don't think there would be problems upto fairly big numbers.
– PradyumanDixit
Dec 14 at 14:48
@DavidLavender If the array were long enough to overflow the stack, the output would be too big to fit in this universe.
– Solomonoff's Secret
Dec 14 at 18:14
Thanks PradyumanDixit I'll go with @TimBiegeleisen solution. Voted up through.
– Oleg Caralanski
Dec 14 at 14:06
Thanks PradyumanDixit I'll go with @TimBiegeleisen solution. Voted up through.
– Oleg Caralanski
Dec 14 at 14:06
2
2
Worth pointing out that recursion has its own problems: too many iterations and you'll get a StackOverflowException
– David Lavender
Dec 14 at 14:25
Worth pointing out that recursion has its own problems: too many iterations and you'll get a StackOverflowException
– David Lavender
Dec 14 at 14:25
2
2
Small addition, but prefer writing the array brackets before the name and after the type:
int data
and not C style int data
– Lino
Dec 14 at 14:37
Small addition, but prefer writing the array brackets before the name and after the type:
int data
and not C style int data
– Lino
Dec 14 at 14:37
@DavidLavender, yes, but, with recursion in this code, I don't think there would be problems upto fairly big numbers.
– PradyumanDixit
Dec 14 at 14:48
@DavidLavender, yes, but, with recursion in this code, I don't think there would be problems upto fairly big numbers.
– PradyumanDixit
Dec 14 at 14:48
@DavidLavender If the array were long enough to overflow the stack, the output would be too big to fit in this universe.
– Solomonoff's Secret
Dec 14 at 18:14
@DavidLavender If the array were long enough to overflow the stack, the output would be too big to fit in this universe.
– Solomonoff's Secret
Dec 14 at 18:14
add a comment |
This sounds like a textbook case for a recursive solution:
public static void combineAndPrint(String pieces, String operators) {
if (pieces.length < 1) {
// no pieces? do nothing!
} else if (pieces.length == 1) {
// just one piece? no need to join anything, just print it!
System.out.println(pieces[0]);
} else {
// make a new array that's one piece shorter
String newPieces = new String[pieces.length - 1];
// copy all but the first two pieces into it
for (int i = 2; i < pieces.length; i++) {
newPieces[i - 1] = pieces[i];
}
// combine the first two pieces and recurse
for (int i = 0; i < operators.length; i++) {
newPieces[0] = pieces[0] + operators[i] + pieces[1];
combineAndPrint(newPieces, operators);
}
}
}
public static void main(String args) {
String operators = {"+", "-", "*"};
String numbers = {"48", "24", "12", "6"};
combineAndPrint(numbers, operators);
}
Try it online!
BTW, to generalize this method so that you can do more things with the generated expressions than just printing them, I would recommend making it accept an extra Consumer<String>
parameter. That is, you could rewrite the method declaration as:
public static void combine(String pieces, String operators, Consumer<String> consumer) {
and replace the System.out.println(pieces[0])
with consumer.accept(pieces[0])
and the recursive call to combineAndPrint(newPieces, operators)
with combine(newPieces, operators, consumer)
. Then just call it from your main method e.g. as:
combine(numbers, operators, s -> System.out.println(s));
Try it online!
(Of course, doing it in this more flexible way requires a somewhat modern Java version — Java 8 or later, to be specific — whereas the first example I showed above should work on even ancient versions all the way down to Java 1.0. Maybe in some future version of Java we'll get proper support for coroutines and generators, like Python and Kotlin and even modern JS already have, and then we won't even need to pass the consumer around any more.)
This should be accepted.
– Eric Wang
Dec 14 at 20:18
It also worked. Thanks you! Voted-up. Thank you Ilmari!
– Oleg Caralanski
Dec 15 at 7:43
@IlmariKaronen Isn't more correct to iterate starting from 1 and not from 2?for (int i = 1; i < pieces.length; i++)
– Oleg Caralanski
Dec 17 at 9:42
@OlegCaralanski: We want to copy all but the first two elements ofpieces
intonewPieces
, leaving the first slot ofnewPieces
free for the combination of the first two elements ofpieces
. We can do this with eitherfor (int i = 2; i < pieces.length; i++) newPieces[i - 1] = pieces[i];
orfor (int i = 1; i < newPieces.length; i++) newPieces[i] = pieces[i + 1];
. Either way works. (Of course, it also wouldn't break anything if we started either loop one element earlier, but then we'd be doing useless work by copyingpieces[1]
intonewPieces[0]
only for it to be overwritten below.)
– Ilmari Karonen
Dec 17 at 14:20
add a comment |
This sounds like a textbook case for a recursive solution:
public static void combineAndPrint(String pieces, String operators) {
if (pieces.length < 1) {
// no pieces? do nothing!
} else if (pieces.length == 1) {
// just one piece? no need to join anything, just print it!
System.out.println(pieces[0]);
} else {
// make a new array that's one piece shorter
String newPieces = new String[pieces.length - 1];
// copy all but the first two pieces into it
for (int i = 2; i < pieces.length; i++) {
newPieces[i - 1] = pieces[i];
}
// combine the first two pieces and recurse
for (int i = 0; i < operators.length; i++) {
newPieces[0] = pieces[0] + operators[i] + pieces[1];
combineAndPrint(newPieces, operators);
}
}
}
public static void main(String args) {
String operators = {"+", "-", "*"};
String numbers = {"48", "24", "12", "6"};
combineAndPrint(numbers, operators);
}
Try it online!
BTW, to generalize this method so that you can do more things with the generated expressions than just printing them, I would recommend making it accept an extra Consumer<String>
parameter. That is, you could rewrite the method declaration as:
public static void combine(String pieces, String operators, Consumer<String> consumer) {
and replace the System.out.println(pieces[0])
with consumer.accept(pieces[0])
and the recursive call to combineAndPrint(newPieces, operators)
with combine(newPieces, operators, consumer)
. Then just call it from your main method e.g. as:
combine(numbers, operators, s -> System.out.println(s));
Try it online!
(Of course, doing it in this more flexible way requires a somewhat modern Java version — Java 8 or later, to be specific — whereas the first example I showed above should work on even ancient versions all the way down to Java 1.0. Maybe in some future version of Java we'll get proper support for coroutines and generators, like Python and Kotlin and even modern JS already have, and then we won't even need to pass the consumer around any more.)
This should be accepted.
– Eric Wang
Dec 14 at 20:18
It also worked. Thanks you! Voted-up. Thank you Ilmari!
– Oleg Caralanski
Dec 15 at 7:43
@IlmariKaronen Isn't more correct to iterate starting from 1 and not from 2?for (int i = 1; i < pieces.length; i++)
– Oleg Caralanski
Dec 17 at 9:42
@OlegCaralanski: We want to copy all but the first two elements ofpieces
intonewPieces
, leaving the first slot ofnewPieces
free for the combination of the first two elements ofpieces
. We can do this with eitherfor (int i = 2; i < pieces.length; i++) newPieces[i - 1] = pieces[i];
orfor (int i = 1; i < newPieces.length; i++) newPieces[i] = pieces[i + 1];
. Either way works. (Of course, it also wouldn't break anything if we started either loop one element earlier, but then we'd be doing useless work by copyingpieces[1]
intonewPieces[0]
only for it to be overwritten below.)
– Ilmari Karonen
Dec 17 at 14:20
add a comment |
This sounds like a textbook case for a recursive solution:
public static void combineAndPrint(String pieces, String operators) {
if (pieces.length < 1) {
// no pieces? do nothing!
} else if (pieces.length == 1) {
// just one piece? no need to join anything, just print it!
System.out.println(pieces[0]);
} else {
// make a new array that's one piece shorter
String newPieces = new String[pieces.length - 1];
// copy all but the first two pieces into it
for (int i = 2; i < pieces.length; i++) {
newPieces[i - 1] = pieces[i];
}
// combine the first two pieces and recurse
for (int i = 0; i < operators.length; i++) {
newPieces[0] = pieces[0] + operators[i] + pieces[1];
combineAndPrint(newPieces, operators);
}
}
}
public static void main(String args) {
String operators = {"+", "-", "*"};
String numbers = {"48", "24", "12", "6"};
combineAndPrint(numbers, operators);
}
Try it online!
BTW, to generalize this method so that you can do more things with the generated expressions than just printing them, I would recommend making it accept an extra Consumer<String>
parameter. That is, you could rewrite the method declaration as:
public static void combine(String pieces, String operators, Consumer<String> consumer) {
and replace the System.out.println(pieces[0])
with consumer.accept(pieces[0])
and the recursive call to combineAndPrint(newPieces, operators)
with combine(newPieces, operators, consumer)
. Then just call it from your main method e.g. as:
combine(numbers, operators, s -> System.out.println(s));
Try it online!
(Of course, doing it in this more flexible way requires a somewhat modern Java version — Java 8 or later, to be specific — whereas the first example I showed above should work on even ancient versions all the way down to Java 1.0. Maybe in some future version of Java we'll get proper support for coroutines and generators, like Python and Kotlin and even modern JS already have, and then we won't even need to pass the consumer around any more.)
This sounds like a textbook case for a recursive solution:
public static void combineAndPrint(String pieces, String operators) {
if (pieces.length < 1) {
// no pieces? do nothing!
} else if (pieces.length == 1) {
// just one piece? no need to join anything, just print it!
System.out.println(pieces[0]);
} else {
// make a new array that's one piece shorter
String newPieces = new String[pieces.length - 1];
// copy all but the first two pieces into it
for (int i = 2; i < pieces.length; i++) {
newPieces[i - 1] = pieces[i];
}
// combine the first two pieces and recurse
for (int i = 0; i < operators.length; i++) {
newPieces[0] = pieces[0] + operators[i] + pieces[1];
combineAndPrint(newPieces, operators);
}
}
}
public static void main(String args) {
String operators = {"+", "-", "*"};
String numbers = {"48", "24", "12", "6"};
combineAndPrint(numbers, operators);
}
Try it online!
BTW, to generalize this method so that you can do more things with the generated expressions than just printing them, I would recommend making it accept an extra Consumer<String>
parameter. That is, you could rewrite the method declaration as:
public static void combine(String pieces, String operators, Consumer<String> consumer) {
and replace the System.out.println(pieces[0])
with consumer.accept(pieces[0])
and the recursive call to combineAndPrint(newPieces, operators)
with combine(newPieces, operators, consumer)
. Then just call it from your main method e.g. as:
combine(numbers, operators, s -> System.out.println(s));
Try it online!
(Of course, doing it in this more flexible way requires a somewhat modern Java version — Java 8 or later, to be specific — whereas the first example I showed above should work on even ancient versions all the way down to Java 1.0. Maybe in some future version of Java we'll get proper support for coroutines and generators, like Python and Kotlin and even modern JS already have, and then we won't even need to pass the consumer around any more.)
answered Dec 14 at 15:29
Ilmari Karonen
37k566124
37k566124
This should be accepted.
– Eric Wang
Dec 14 at 20:18
It also worked. Thanks you! Voted-up. Thank you Ilmari!
– Oleg Caralanski
Dec 15 at 7:43
@IlmariKaronen Isn't more correct to iterate starting from 1 and not from 2?for (int i = 1; i < pieces.length; i++)
– Oleg Caralanski
Dec 17 at 9:42
@OlegCaralanski: We want to copy all but the first two elements ofpieces
intonewPieces
, leaving the first slot ofnewPieces
free for the combination of the first two elements ofpieces
. We can do this with eitherfor (int i = 2; i < pieces.length; i++) newPieces[i - 1] = pieces[i];
orfor (int i = 1; i < newPieces.length; i++) newPieces[i] = pieces[i + 1];
. Either way works. (Of course, it also wouldn't break anything if we started either loop one element earlier, but then we'd be doing useless work by copyingpieces[1]
intonewPieces[0]
only for it to be overwritten below.)
– Ilmari Karonen
Dec 17 at 14:20
add a comment |
This should be accepted.
– Eric Wang
Dec 14 at 20:18
It also worked. Thanks you! Voted-up. Thank you Ilmari!
– Oleg Caralanski
Dec 15 at 7:43
@IlmariKaronen Isn't more correct to iterate starting from 1 and not from 2?for (int i = 1; i < pieces.length; i++)
– Oleg Caralanski
Dec 17 at 9:42
@OlegCaralanski: We want to copy all but the first two elements ofpieces
intonewPieces
, leaving the first slot ofnewPieces
free for the combination of the first two elements ofpieces
. We can do this with eitherfor (int i = 2; i < pieces.length; i++) newPieces[i - 1] = pieces[i];
orfor (int i = 1; i < newPieces.length; i++) newPieces[i] = pieces[i + 1];
. Either way works. (Of course, it also wouldn't break anything if we started either loop one element earlier, but then we'd be doing useless work by copyingpieces[1]
intonewPieces[0]
only for it to be overwritten below.)
– Ilmari Karonen
Dec 17 at 14:20
This should be accepted.
– Eric Wang
Dec 14 at 20:18
This should be accepted.
– Eric Wang
Dec 14 at 20:18
It also worked. Thanks you! Voted-up. Thank you Ilmari!
– Oleg Caralanski
Dec 15 at 7:43
It also worked. Thanks you! Voted-up. Thank you Ilmari!
– Oleg Caralanski
Dec 15 at 7:43
@IlmariKaronen Isn't more correct to iterate starting from 1 and not from 2?
for (int i = 1; i < pieces.length; i++)
– Oleg Caralanski
Dec 17 at 9:42
@IlmariKaronen Isn't more correct to iterate starting from 1 and not from 2?
for (int i = 1; i < pieces.length; i++)
– Oleg Caralanski
Dec 17 at 9:42
@OlegCaralanski: We want to copy all but the first two elements of
pieces
into newPieces
, leaving the first slot of newPieces
free for the combination of the first two elements of pieces
. We can do this with either for (int i = 2; i < pieces.length; i++) newPieces[i - 1] = pieces[i];
or for (int i = 1; i < newPieces.length; i++) newPieces[i] = pieces[i + 1];
. Either way works. (Of course, it also wouldn't break anything if we started either loop one element earlier, but then we'd be doing useless work by copying pieces[1]
into newPieces[0]
only for it to be overwritten below.)– Ilmari Karonen
Dec 17 at 14:20
@OlegCaralanski: We want to copy all but the first two elements of
pieces
into newPieces
, leaving the first slot of newPieces
free for the combination of the first two elements of pieces
. We can do this with either for (int i = 2; i < pieces.length; i++) newPieces[i - 1] = pieces[i];
or for (int i = 1; i < newPieces.length; i++) newPieces[i] = pieces[i + 1];
. Either way works. (Of course, it also wouldn't break anything if we started either loop one element earlier, but then we'd be doing useless work by copying pieces[1]
into newPieces[0]
only for it to be overwritten below.)– Ilmari Karonen
Dec 17 at 14:20
add a comment |
I made an alternative, overengineered (but flexible!) "business" solution. The array lengths and values (numbers
and operators
) can be flexible.
package test1;
import java.io.IOException;
import java.util.ArrayList;
public class MainClass
{
public static void main(String args) throws IOException
{
String operators = {"+", "-", "*"};
int numbers = {48, 24, 12, 6};
ArrayList<String> strings = new MainClass().getAllPossibleCombinations(numbers, operators);
for (String string : strings)
{
System.out.println(string);
}
}
private ArrayList<String> getAllPossibleCombinations(int numbers, String operators)
{
if (numbers.length < 2) throw new IllegalArgumentException("Length of numbers-array must be at least 2");
if (operators.length < 1) throw new IllegalArgumentException("Length of operators-array must be at least 1");
ArrayList<String> returnList = new ArrayList<>();
int indexes = new int[numbers.length - 1];
while (true)
{
StringBuilder line = new StringBuilder();
for (int i = 0; i < numbers.length; i++)
{
int number = numbers[i];
line.append(number);
if (i < indexes.length)
{
line.append(operators[indexes[i]]);
}
}
returnList.add(line.toString());
try
{
this.updateIndexes(indexes, operators.length - 1);
}
catch (NoMoreCombinationsException e)
{
break;
}
}
return returnList;
}
private void updateIndexes(int currentIndexes, int maxValue) throws NoMoreCombinationsException
{
if (this.intArrayIsOnly(currentIndexes, maxValue))
{
throw new NoMoreCombinationsException();
}
for (int i = currentIndexes.length - 1; i >= 0; i--)
{
int currentIndex = currentIndexes[i];
if (currentIndex < maxValue)
{
currentIndexes[i] = currentIndex + 1;
break;
}
else
{
currentIndexes[i] = 0;
}
}
}
private boolean intArrayIsOnly(int array, int value)
{
for (int iteratedValue : array)
{
if (iteratedValue != value) return false;
}
return true;
}
}
class NoMoreCombinationsException extends Exception
{
public NoMoreCombinationsException()
{
}
public NoMoreCombinationsException(String message)
{
super(message);
}
public NoMoreCombinationsException(String message, Throwable cause)
{
super(message, cause);
}
public NoMoreCombinationsException(Throwable cause)
{
super(cause);
}
public NoMoreCombinationsException(String message, Throwable cause, boolean enableSuppression, boolean writableStackTrace)
{
super(message, cause, enableSuppression, writableStackTrace);
}
}
Works like a charm :)
Kudos for writing clean, executable and self explanatory code :)
– PradyumanDixit
Dec 14 at 14:47
Thank you too Impulse! Voted up through.
– Oleg Caralanski
Dec 14 at 14:54
I wouldn't call it printAllPossible... That method doesn't actually print anything. Maybe generate.
– findusl
Dec 14 at 16:41
2
You can simplify this... Make your methods static and return aboolean
inupdateIndexes
. Avoid using exceptions in flow-control; and, favor the interfaceList
instead of theArrayList
implementation in your APIs.
– Jan Nielsen
Dec 14 at 17:53
add a comment |
I made an alternative, overengineered (but flexible!) "business" solution. The array lengths and values (numbers
and operators
) can be flexible.
package test1;
import java.io.IOException;
import java.util.ArrayList;
public class MainClass
{
public static void main(String args) throws IOException
{
String operators = {"+", "-", "*"};
int numbers = {48, 24, 12, 6};
ArrayList<String> strings = new MainClass().getAllPossibleCombinations(numbers, operators);
for (String string : strings)
{
System.out.println(string);
}
}
private ArrayList<String> getAllPossibleCombinations(int numbers, String operators)
{
if (numbers.length < 2) throw new IllegalArgumentException("Length of numbers-array must be at least 2");
if (operators.length < 1) throw new IllegalArgumentException("Length of operators-array must be at least 1");
ArrayList<String> returnList = new ArrayList<>();
int indexes = new int[numbers.length - 1];
while (true)
{
StringBuilder line = new StringBuilder();
for (int i = 0; i < numbers.length; i++)
{
int number = numbers[i];
line.append(number);
if (i < indexes.length)
{
line.append(operators[indexes[i]]);
}
}
returnList.add(line.toString());
try
{
this.updateIndexes(indexes, operators.length - 1);
}
catch (NoMoreCombinationsException e)
{
break;
}
}
return returnList;
}
private void updateIndexes(int currentIndexes, int maxValue) throws NoMoreCombinationsException
{
if (this.intArrayIsOnly(currentIndexes, maxValue))
{
throw new NoMoreCombinationsException();
}
for (int i = currentIndexes.length - 1; i >= 0; i--)
{
int currentIndex = currentIndexes[i];
if (currentIndex < maxValue)
{
currentIndexes[i] = currentIndex + 1;
break;
}
else
{
currentIndexes[i] = 0;
}
}
}
private boolean intArrayIsOnly(int array, int value)
{
for (int iteratedValue : array)
{
if (iteratedValue != value) return false;
}
return true;
}
}
class NoMoreCombinationsException extends Exception
{
public NoMoreCombinationsException()
{
}
public NoMoreCombinationsException(String message)
{
super(message);
}
public NoMoreCombinationsException(String message, Throwable cause)
{
super(message, cause);
}
public NoMoreCombinationsException(Throwable cause)
{
super(cause);
}
public NoMoreCombinationsException(String message, Throwable cause, boolean enableSuppression, boolean writableStackTrace)
{
super(message, cause, enableSuppression, writableStackTrace);
}
}
Works like a charm :)
Kudos for writing clean, executable and self explanatory code :)
– PradyumanDixit
Dec 14 at 14:47
Thank you too Impulse! Voted up through.
– Oleg Caralanski
Dec 14 at 14:54
I wouldn't call it printAllPossible... That method doesn't actually print anything. Maybe generate.
– findusl
Dec 14 at 16:41
2
You can simplify this... Make your methods static and return aboolean
inupdateIndexes
. Avoid using exceptions in flow-control; and, favor the interfaceList
instead of theArrayList
implementation in your APIs.
– Jan Nielsen
Dec 14 at 17:53
add a comment |
I made an alternative, overengineered (but flexible!) "business" solution. The array lengths and values (numbers
and operators
) can be flexible.
package test1;
import java.io.IOException;
import java.util.ArrayList;
public class MainClass
{
public static void main(String args) throws IOException
{
String operators = {"+", "-", "*"};
int numbers = {48, 24, 12, 6};
ArrayList<String> strings = new MainClass().getAllPossibleCombinations(numbers, operators);
for (String string : strings)
{
System.out.println(string);
}
}
private ArrayList<String> getAllPossibleCombinations(int numbers, String operators)
{
if (numbers.length < 2) throw new IllegalArgumentException("Length of numbers-array must be at least 2");
if (operators.length < 1) throw new IllegalArgumentException("Length of operators-array must be at least 1");
ArrayList<String> returnList = new ArrayList<>();
int indexes = new int[numbers.length - 1];
while (true)
{
StringBuilder line = new StringBuilder();
for (int i = 0; i < numbers.length; i++)
{
int number = numbers[i];
line.append(number);
if (i < indexes.length)
{
line.append(operators[indexes[i]]);
}
}
returnList.add(line.toString());
try
{
this.updateIndexes(indexes, operators.length - 1);
}
catch (NoMoreCombinationsException e)
{
break;
}
}
return returnList;
}
private void updateIndexes(int currentIndexes, int maxValue) throws NoMoreCombinationsException
{
if (this.intArrayIsOnly(currentIndexes, maxValue))
{
throw new NoMoreCombinationsException();
}
for (int i = currentIndexes.length - 1; i >= 0; i--)
{
int currentIndex = currentIndexes[i];
if (currentIndex < maxValue)
{
currentIndexes[i] = currentIndex + 1;
break;
}
else
{
currentIndexes[i] = 0;
}
}
}
private boolean intArrayIsOnly(int array, int value)
{
for (int iteratedValue : array)
{
if (iteratedValue != value) return false;
}
return true;
}
}
class NoMoreCombinationsException extends Exception
{
public NoMoreCombinationsException()
{
}
public NoMoreCombinationsException(String message)
{
super(message);
}
public NoMoreCombinationsException(String message, Throwable cause)
{
super(message, cause);
}
public NoMoreCombinationsException(Throwable cause)
{
super(cause);
}
public NoMoreCombinationsException(String message, Throwable cause, boolean enableSuppression, boolean writableStackTrace)
{
super(message, cause, enableSuppression, writableStackTrace);
}
}
Works like a charm :)
I made an alternative, overengineered (but flexible!) "business" solution. The array lengths and values (numbers
and operators
) can be flexible.
package test1;
import java.io.IOException;
import java.util.ArrayList;
public class MainClass
{
public static void main(String args) throws IOException
{
String operators = {"+", "-", "*"};
int numbers = {48, 24, 12, 6};
ArrayList<String> strings = new MainClass().getAllPossibleCombinations(numbers, operators);
for (String string : strings)
{
System.out.println(string);
}
}
private ArrayList<String> getAllPossibleCombinations(int numbers, String operators)
{
if (numbers.length < 2) throw new IllegalArgumentException("Length of numbers-array must be at least 2");
if (operators.length < 1) throw new IllegalArgumentException("Length of operators-array must be at least 1");
ArrayList<String> returnList = new ArrayList<>();
int indexes = new int[numbers.length - 1];
while (true)
{
StringBuilder line = new StringBuilder();
for (int i = 0; i < numbers.length; i++)
{
int number = numbers[i];
line.append(number);
if (i < indexes.length)
{
line.append(operators[indexes[i]]);
}
}
returnList.add(line.toString());
try
{
this.updateIndexes(indexes, operators.length - 1);
}
catch (NoMoreCombinationsException e)
{
break;
}
}
return returnList;
}
private void updateIndexes(int currentIndexes, int maxValue) throws NoMoreCombinationsException
{
if (this.intArrayIsOnly(currentIndexes, maxValue))
{
throw new NoMoreCombinationsException();
}
for (int i = currentIndexes.length - 1; i >= 0; i--)
{
int currentIndex = currentIndexes[i];
if (currentIndex < maxValue)
{
currentIndexes[i] = currentIndex + 1;
break;
}
else
{
currentIndexes[i] = 0;
}
}
}
private boolean intArrayIsOnly(int array, int value)
{
for (int iteratedValue : array)
{
if (iteratedValue != value) return false;
}
return true;
}
}
class NoMoreCombinationsException extends Exception
{
public NoMoreCombinationsException()
{
}
public NoMoreCombinationsException(String message)
{
super(message);
}
public NoMoreCombinationsException(String message, Throwable cause)
{
super(message, cause);
}
public NoMoreCombinationsException(Throwable cause)
{
super(cause);
}
public NoMoreCombinationsException(String message, Throwable cause, boolean enableSuppression, boolean writableStackTrace)
{
super(message, cause, enableSuppression, writableStackTrace);
}
}
Works like a charm :)
edited Dec 14 at 17:09
answered Dec 14 at 14:45
Impulse The Fox
1,69011327
1,69011327
Kudos for writing clean, executable and self explanatory code :)
– PradyumanDixit
Dec 14 at 14:47
Thank you too Impulse! Voted up through.
– Oleg Caralanski
Dec 14 at 14:54
I wouldn't call it printAllPossible... That method doesn't actually print anything. Maybe generate.
– findusl
Dec 14 at 16:41
2
You can simplify this... Make your methods static and return aboolean
inupdateIndexes
. Avoid using exceptions in flow-control; and, favor the interfaceList
instead of theArrayList
implementation in your APIs.
– Jan Nielsen
Dec 14 at 17:53
add a comment |
Kudos for writing clean, executable and self explanatory code :)
– PradyumanDixit
Dec 14 at 14:47
Thank you too Impulse! Voted up through.
– Oleg Caralanski
Dec 14 at 14:54
I wouldn't call it printAllPossible... That method doesn't actually print anything. Maybe generate.
– findusl
Dec 14 at 16:41
2
You can simplify this... Make your methods static and return aboolean
inupdateIndexes
. Avoid using exceptions in flow-control; and, favor the interfaceList
instead of theArrayList
implementation in your APIs.
– Jan Nielsen
Dec 14 at 17:53
Kudos for writing clean, executable and self explanatory code :)
– PradyumanDixit
Dec 14 at 14:47
Kudos for writing clean, executable and self explanatory code :)
– PradyumanDixit
Dec 14 at 14:47
Thank you too Impulse! Voted up through.
– Oleg Caralanski
Dec 14 at 14:54
Thank you too Impulse! Voted up through.
– Oleg Caralanski
Dec 14 at 14:54
I wouldn't call it printAllPossible... That method doesn't actually print anything. Maybe generate.
– findusl
Dec 14 at 16:41
I wouldn't call it printAllPossible... That method doesn't actually print anything. Maybe generate.
– findusl
Dec 14 at 16:41
2
2
You can simplify this... Make your methods static and return a
boolean
in updateIndexes
. Avoid using exceptions in flow-control; and, favor the interface List
instead of the ArrayList
implementation in your APIs.– Jan Nielsen
Dec 14 at 17:53
You can simplify this... Make your methods static and return a
boolean
in updateIndexes
. Avoid using exceptions in flow-control; and, favor the interface List
instead of the ArrayList
implementation in your APIs.– Jan Nielsen
Dec 14 at 17:53
add a comment |
As already pointed out by findusl in his answer, the problem here is, strictly speaking, not to find any sort of "combination of two arrays". Instead, you basically just want to find all possible combinations of the available operators.
(The fact that you later want to "interveave" them with operands is rather unrelated to the core of the question)
So here is another option for solving this: You can create an iterable over all combinations of a certain number of elements from a certain set (in your case: the operators) and then simply combine the results with the other set (in your case: the operands).
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
public class OperatorsTest
{
public static void main(String args)
{
String operators = {"+", "-", "*"};
int numbers = {48, 24, 12, 6};
CombinationIterable<String> iterable =
new CombinationIterable<String>(3, Arrays.asList(operators));
for (List<String> element : iterable)
{
System.out.println(interveave(element, numbers));
}
}
private static String interveave(List<String> operators, int numbers)
{
StringBuilder sb = new StringBuilder();
for (int i=0; i<operators.size(); i++)
{
sb.append(numbers[i]);
sb.append(operators.get(i));
}
sb.append(numbers[numbers.length-1]);
return sb.toString();
}
}
class CombinationIterable<T> implements Iterable<List<T>>
{
private final List<T> input;
private final int sampleSize;
private final int numElements;
public CombinationIterable(int sampleSize, List<T> input)
{
this.sampleSize = sampleSize;
this.input = input;
numElements = (int) Math.pow(input.size(), sampleSize);
}
@Override
public Iterator<List<T>> iterator()
{
return new Iterator<List<T>>()
{
private int current = 0;
private final int chosen = new int[sampleSize];
@Override
public boolean hasNext()
{
return current < numElements;
}
@Override
public List<T> next()
{
if (!hasNext())
{
throw new NoSuchElementException("No more elements");
}
List<T> result = new ArrayList<T>(sampleSize);
for (int i = 0; i < sampleSize; i++)
{
result.add(input.get(chosen[i]));
}
increase();
current++;
return result;
}
private void increase()
{
int index = chosen.length - 1;
while (index >= 0)
{
if (chosen[index] < input.size() - 1)
{
chosen[index]++;
return;
}
chosen[index] = 0;
index--;
}
}
};
}
}
The task resembles that of finding a set of operations that can be done with a certain number of operands and operators, and thus, this Q/A may be related. But whether or not things like associativity or commutativity should be considered here was not mentioned in the question.
It also worked. Voted-up! Thank you Marco!
– Oleg Caralanski
Dec 15 at 7:39
add a comment |
As already pointed out by findusl in his answer, the problem here is, strictly speaking, not to find any sort of "combination of two arrays". Instead, you basically just want to find all possible combinations of the available operators.
(The fact that you later want to "interveave" them with operands is rather unrelated to the core of the question)
So here is another option for solving this: You can create an iterable over all combinations of a certain number of elements from a certain set (in your case: the operators) and then simply combine the results with the other set (in your case: the operands).
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
public class OperatorsTest
{
public static void main(String args)
{
String operators = {"+", "-", "*"};
int numbers = {48, 24, 12, 6};
CombinationIterable<String> iterable =
new CombinationIterable<String>(3, Arrays.asList(operators));
for (List<String> element : iterable)
{
System.out.println(interveave(element, numbers));
}
}
private static String interveave(List<String> operators, int numbers)
{
StringBuilder sb = new StringBuilder();
for (int i=0; i<operators.size(); i++)
{
sb.append(numbers[i]);
sb.append(operators.get(i));
}
sb.append(numbers[numbers.length-1]);
return sb.toString();
}
}
class CombinationIterable<T> implements Iterable<List<T>>
{
private final List<T> input;
private final int sampleSize;
private final int numElements;
public CombinationIterable(int sampleSize, List<T> input)
{
this.sampleSize = sampleSize;
this.input = input;
numElements = (int) Math.pow(input.size(), sampleSize);
}
@Override
public Iterator<List<T>> iterator()
{
return new Iterator<List<T>>()
{
private int current = 0;
private final int chosen = new int[sampleSize];
@Override
public boolean hasNext()
{
return current < numElements;
}
@Override
public List<T> next()
{
if (!hasNext())
{
throw new NoSuchElementException("No more elements");
}
List<T> result = new ArrayList<T>(sampleSize);
for (int i = 0; i < sampleSize; i++)
{
result.add(input.get(chosen[i]));
}
increase();
current++;
return result;
}
private void increase()
{
int index = chosen.length - 1;
while (index >= 0)
{
if (chosen[index] < input.size() - 1)
{
chosen[index]++;
return;
}
chosen[index] = 0;
index--;
}
}
};
}
}
The task resembles that of finding a set of operations that can be done with a certain number of operands and operators, and thus, this Q/A may be related. But whether or not things like associativity or commutativity should be considered here was not mentioned in the question.
It also worked. Voted-up! Thank you Marco!
– Oleg Caralanski
Dec 15 at 7:39
add a comment |
As already pointed out by findusl in his answer, the problem here is, strictly speaking, not to find any sort of "combination of two arrays". Instead, you basically just want to find all possible combinations of the available operators.
(The fact that you later want to "interveave" them with operands is rather unrelated to the core of the question)
So here is another option for solving this: You can create an iterable over all combinations of a certain number of elements from a certain set (in your case: the operators) and then simply combine the results with the other set (in your case: the operands).
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
public class OperatorsTest
{
public static void main(String args)
{
String operators = {"+", "-", "*"};
int numbers = {48, 24, 12, 6};
CombinationIterable<String> iterable =
new CombinationIterable<String>(3, Arrays.asList(operators));
for (List<String> element : iterable)
{
System.out.println(interveave(element, numbers));
}
}
private static String interveave(List<String> operators, int numbers)
{
StringBuilder sb = new StringBuilder();
for (int i=0; i<operators.size(); i++)
{
sb.append(numbers[i]);
sb.append(operators.get(i));
}
sb.append(numbers[numbers.length-1]);
return sb.toString();
}
}
class CombinationIterable<T> implements Iterable<List<T>>
{
private final List<T> input;
private final int sampleSize;
private final int numElements;
public CombinationIterable(int sampleSize, List<T> input)
{
this.sampleSize = sampleSize;
this.input = input;
numElements = (int) Math.pow(input.size(), sampleSize);
}
@Override
public Iterator<List<T>> iterator()
{
return new Iterator<List<T>>()
{
private int current = 0;
private final int chosen = new int[sampleSize];
@Override
public boolean hasNext()
{
return current < numElements;
}
@Override
public List<T> next()
{
if (!hasNext())
{
throw new NoSuchElementException("No more elements");
}
List<T> result = new ArrayList<T>(sampleSize);
for (int i = 0; i < sampleSize; i++)
{
result.add(input.get(chosen[i]));
}
increase();
current++;
return result;
}
private void increase()
{
int index = chosen.length - 1;
while (index >= 0)
{
if (chosen[index] < input.size() - 1)
{
chosen[index]++;
return;
}
chosen[index] = 0;
index--;
}
}
};
}
}
The task resembles that of finding a set of operations that can be done with a certain number of operands and operators, and thus, this Q/A may be related. But whether or not things like associativity or commutativity should be considered here was not mentioned in the question.
As already pointed out by findusl in his answer, the problem here is, strictly speaking, not to find any sort of "combination of two arrays". Instead, you basically just want to find all possible combinations of the available operators.
(The fact that you later want to "interveave" them with operands is rather unrelated to the core of the question)
So here is another option for solving this: You can create an iterable over all combinations of a certain number of elements from a certain set (in your case: the operators) and then simply combine the results with the other set (in your case: the operands).
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
public class OperatorsTest
{
public static void main(String args)
{
String operators = {"+", "-", "*"};
int numbers = {48, 24, 12, 6};
CombinationIterable<String> iterable =
new CombinationIterable<String>(3, Arrays.asList(operators));
for (List<String> element : iterable)
{
System.out.println(interveave(element, numbers));
}
}
private static String interveave(List<String> operators, int numbers)
{
StringBuilder sb = new StringBuilder();
for (int i=0; i<operators.size(); i++)
{
sb.append(numbers[i]);
sb.append(operators.get(i));
}
sb.append(numbers[numbers.length-1]);
return sb.toString();
}
}
class CombinationIterable<T> implements Iterable<List<T>>
{
private final List<T> input;
private final int sampleSize;
private final int numElements;
public CombinationIterable(int sampleSize, List<T> input)
{
this.sampleSize = sampleSize;
this.input = input;
numElements = (int) Math.pow(input.size(), sampleSize);
}
@Override
public Iterator<List<T>> iterator()
{
return new Iterator<List<T>>()
{
private int current = 0;
private final int chosen = new int[sampleSize];
@Override
public boolean hasNext()
{
return current < numElements;
}
@Override
public List<T> next()
{
if (!hasNext())
{
throw new NoSuchElementException("No more elements");
}
List<T> result = new ArrayList<T>(sampleSize);
for (int i = 0; i < sampleSize; i++)
{
result.add(input.get(chosen[i]));
}
increase();
current++;
return result;
}
private void increase()
{
int index = chosen.length - 1;
while (index >= 0)
{
if (chosen[index] < input.size() - 1)
{
chosen[index]++;
return;
}
chosen[index] = 0;
index--;
}
}
};
}
}
The task resembles that of finding a set of operations that can be done with a certain number of operands and operators, and thus, this Q/A may be related. But whether or not things like associativity or commutativity should be considered here was not mentioned in the question.
edited Dec 14 at 19:45
answered Dec 14 at 18:46
Marco13
41.7k854107
41.7k854107
It also worked. Voted-up! Thank you Marco!
– Oleg Caralanski
Dec 15 at 7:39
add a comment |
It also worked. Voted-up! Thank you Marco!
– Oleg Caralanski
Dec 15 at 7:39
It also worked. Voted-up! Thank you Marco!
– Oleg Caralanski
Dec 15 at 7:39
It also worked. Voted-up! Thank you Marco!
– Oleg Caralanski
Dec 15 at 7:39
add a comment |
A bit of background information why the answers are they way they are. This problem is not really called "all possible combinations" as that is usually the problem where you can represent the elements as bits and switch them to 0 or 1 whether the element is included or not. This has a complexity of 2^N where N is the amount of operators you have. This can be solved easily in a single loop.
However in your case you have the "urn problem with replacement and sequence". The complexity of this is N^n where n is the amount of spots you have to fill with operators. (This is often seen for pincodes where each spots can be 10 values). So because this is of higher complexity than the "all possible combinations" problem you need multiple loops or recursive calls.
So to answer the question, "how to solve this?". You have to solve it with multiple loops or recursion because of the underlying problem's complexity.
add a comment |
A bit of background information why the answers are they way they are. This problem is not really called "all possible combinations" as that is usually the problem where you can represent the elements as bits and switch them to 0 or 1 whether the element is included or not. This has a complexity of 2^N where N is the amount of operators you have. This can be solved easily in a single loop.
However in your case you have the "urn problem with replacement and sequence". The complexity of this is N^n where n is the amount of spots you have to fill with operators. (This is often seen for pincodes where each spots can be 10 values). So because this is of higher complexity than the "all possible combinations" problem you need multiple loops or recursive calls.
So to answer the question, "how to solve this?". You have to solve it with multiple loops or recursion because of the underlying problem's complexity.
add a comment |
A bit of background information why the answers are they way they are. This problem is not really called "all possible combinations" as that is usually the problem where you can represent the elements as bits and switch them to 0 or 1 whether the element is included or not. This has a complexity of 2^N where N is the amount of operators you have. This can be solved easily in a single loop.
However in your case you have the "urn problem with replacement and sequence". The complexity of this is N^n where n is the amount of spots you have to fill with operators. (This is often seen for pincodes where each spots can be 10 values). So because this is of higher complexity than the "all possible combinations" problem you need multiple loops or recursive calls.
So to answer the question, "how to solve this?". You have to solve it with multiple loops or recursion because of the underlying problem's complexity.
A bit of background information why the answers are they way they are. This problem is not really called "all possible combinations" as that is usually the problem where you can represent the elements as bits and switch them to 0 or 1 whether the element is included or not. This has a complexity of 2^N where N is the amount of operators you have. This can be solved easily in a single loop.
However in your case you have the "urn problem with replacement and sequence". The complexity of this is N^n where n is the amount of spots you have to fill with operators. (This is often seen for pincodes where each spots can be 10 values). So because this is of higher complexity than the "all possible combinations" problem you need multiple loops or recursive calls.
So to answer the question, "how to solve this?". You have to solve it with multiple loops or recursion because of the underlying problem's complexity.
edited Dec 14 at 16:44
answered Dec 14 at 16:25
findusl
739726
739726
add a comment |
add a comment |
You don't need multiple loops or recursion.
Here's an example showcasing a limited number of loops and no recursion at all.
int combine (int values) {
int size = values.length;
int combinations = 1;
for(int i = 0; i < size; i++) {
combinations *= size;
}
// or int combinations = (int)Math.pow(size, size);
int result = new int[combinations][size];
for(int i = 0; i < combinations; i++) {
int index = i;
for(int j = 0; j < size; j++) {
result[i][j] = values[index % size];
index /= size;
}
}
return result;
}
If you use it with three elements, [1, 2, 3]
, as in the code below:
void testCombine() {
int combinations = combine(new int{1, 2, 3});
for(int combination: combinations) {
System.out.println(Arrays.toString(combination));
}
}
You end up with the following result:
[1, 1, 1]
[2, 1, 1]
[3, 1, 1]
[1, 2, 1]
[2, 2, 1]
[3, 2, 1]
[1, 3, 1]
[2, 3, 1]
[3, 3, 1]
[1, 1, 2]
[2, 1, 2]
[3, 1, 2]
[1, 2, 2]
[2, 2, 2]
[3, 2, 2]
[1, 3, 2]
[2, 3, 2]
[3, 3, 2]
[1, 1, 3]
[2, 1, 3]
[3, 1, 3]
[1, 2, 3]
[2, 2, 3]
[3, 2, 3]
[1, 3, 3]
[2, 3, 3]
[3, 3, 3]
add a comment |
You don't need multiple loops or recursion.
Here's an example showcasing a limited number of loops and no recursion at all.
int combine (int values) {
int size = values.length;
int combinations = 1;
for(int i = 0; i < size; i++) {
combinations *= size;
}
// or int combinations = (int)Math.pow(size, size);
int result = new int[combinations][size];
for(int i = 0; i < combinations; i++) {
int index = i;
for(int j = 0; j < size; j++) {
result[i][j] = values[index % size];
index /= size;
}
}
return result;
}
If you use it with three elements, [1, 2, 3]
, as in the code below:
void testCombine() {
int combinations = combine(new int{1, 2, 3});
for(int combination: combinations) {
System.out.println(Arrays.toString(combination));
}
}
You end up with the following result:
[1, 1, 1]
[2, 1, 1]
[3, 1, 1]
[1, 2, 1]
[2, 2, 1]
[3, 2, 1]
[1, 3, 1]
[2, 3, 1]
[3, 3, 1]
[1, 1, 2]
[2, 1, 2]
[3, 1, 2]
[1, 2, 2]
[2, 2, 2]
[3, 2, 2]
[1, 3, 2]
[2, 3, 2]
[3, 3, 2]
[1, 1, 3]
[2, 1, 3]
[3, 1, 3]
[1, 2, 3]
[2, 2, 3]
[3, 2, 3]
[1, 3, 3]
[2, 3, 3]
[3, 3, 3]
add a comment |
You don't need multiple loops or recursion.
Here's an example showcasing a limited number of loops and no recursion at all.
int combine (int values) {
int size = values.length;
int combinations = 1;
for(int i = 0; i < size; i++) {
combinations *= size;
}
// or int combinations = (int)Math.pow(size, size);
int result = new int[combinations][size];
for(int i = 0; i < combinations; i++) {
int index = i;
for(int j = 0; j < size; j++) {
result[i][j] = values[index % size];
index /= size;
}
}
return result;
}
If you use it with three elements, [1, 2, 3]
, as in the code below:
void testCombine() {
int combinations = combine(new int{1, 2, 3});
for(int combination: combinations) {
System.out.println(Arrays.toString(combination));
}
}
You end up with the following result:
[1, 1, 1]
[2, 1, 1]
[3, 1, 1]
[1, 2, 1]
[2, 2, 1]
[3, 2, 1]
[1, 3, 1]
[2, 3, 1]
[3, 3, 1]
[1, 1, 2]
[2, 1, 2]
[3, 1, 2]
[1, 2, 2]
[2, 2, 2]
[3, 2, 2]
[1, 3, 2]
[2, 3, 2]
[3, 3, 2]
[1, 1, 3]
[2, 1, 3]
[3, 1, 3]
[1, 2, 3]
[2, 2, 3]
[3, 2, 3]
[1, 3, 3]
[2, 3, 3]
[3, 3, 3]
You don't need multiple loops or recursion.
Here's an example showcasing a limited number of loops and no recursion at all.
int combine (int values) {
int size = values.length;
int combinations = 1;
for(int i = 0; i < size; i++) {
combinations *= size;
}
// or int combinations = (int)Math.pow(size, size);
int result = new int[combinations][size];
for(int i = 0; i < combinations; i++) {
int index = i;
for(int j = 0; j < size; j++) {
result[i][j] = values[index % size];
index /= size;
}
}
return result;
}
If you use it with three elements, [1, 2, 3]
, as in the code below:
void testCombine() {
int combinations = combine(new int{1, 2, 3});
for(int combination: combinations) {
System.out.println(Arrays.toString(combination));
}
}
You end up with the following result:
[1, 1, 1]
[2, 1, 1]
[3, 1, 1]
[1, 2, 1]
[2, 2, 1]
[3, 2, 1]
[1, 3, 1]
[2, 3, 1]
[3, 3, 1]
[1, 1, 2]
[2, 1, 2]
[3, 1, 2]
[1, 2, 2]
[2, 2, 2]
[3, 2, 2]
[1, 3, 2]
[2, 3, 2]
[3, 3, 2]
[1, 1, 3]
[2, 1, 3]
[3, 1, 3]
[1, 2, 3]
[2, 2, 3]
[3, 2, 3]
[1, 3, 3]
[2, 3, 3]
[3, 3, 3]
edited Dec 15 at 1:02
answered Dec 15 at 0:57
Olivier Grégoire
14.7k1663100
14.7k1663100
add a comment |
add a comment |
I've developed a class that covers this use case and many others. I call it the TallyCounter. Your question would be answered with this class like this:
package app;
import java.util.HashMap;
import java.util.Map;
import app.TallyCounter.Type;
public class App {
public static void main(String args) throws Exception {
Map<Long, String> map = new HashMap<>();
map.put(0l, "+");
map.put(1l, "-");
map.put(2l, "*");
TallyCounter counter = new TallyCounter(3, Type.NORMAL, 2);
do {
System.out.format("48%s24%s12%s6n",
map.get(counter.getArray()[2]),
map.get(counter.getArray()[1]),
map.get(counter.getArray()[0])
);
counter.increment();
} while (!counter.overflowFlag);
}
}
add a comment |
I've developed a class that covers this use case and many others. I call it the TallyCounter. Your question would be answered with this class like this:
package app;
import java.util.HashMap;
import java.util.Map;
import app.TallyCounter.Type;
public class App {
public static void main(String args) throws Exception {
Map<Long, String> map = new HashMap<>();
map.put(0l, "+");
map.put(1l, "-");
map.put(2l, "*");
TallyCounter counter = new TallyCounter(3, Type.NORMAL, 2);
do {
System.out.format("48%s24%s12%s6n",
map.get(counter.getArray()[2]),
map.get(counter.getArray()[1]),
map.get(counter.getArray()[0])
);
counter.increment();
} while (!counter.overflowFlag);
}
}
add a comment |
I've developed a class that covers this use case and many others. I call it the TallyCounter. Your question would be answered with this class like this:
package app;
import java.util.HashMap;
import java.util.Map;
import app.TallyCounter.Type;
public class App {
public static void main(String args) throws Exception {
Map<Long, String> map = new HashMap<>();
map.put(0l, "+");
map.put(1l, "-");
map.put(2l, "*");
TallyCounter counter = new TallyCounter(3, Type.NORMAL, 2);
do {
System.out.format("48%s24%s12%s6n",
map.get(counter.getArray()[2]),
map.get(counter.getArray()[1]),
map.get(counter.getArray()[0])
);
counter.increment();
} while (!counter.overflowFlag);
}
}
I've developed a class that covers this use case and many others. I call it the TallyCounter. Your question would be answered with this class like this:
package app;
import java.util.HashMap;
import java.util.Map;
import app.TallyCounter.Type;
public class App {
public static void main(String args) throws Exception {
Map<Long, String> map = new HashMap<>();
map.put(0l, "+");
map.put(1l, "-");
map.put(2l, "*");
TallyCounter counter = new TallyCounter(3, Type.NORMAL, 2);
do {
System.out.format("48%s24%s12%s6n",
map.get(counter.getArray()[2]),
map.get(counter.getArray()[1]),
map.get(counter.getArray()[0])
);
counter.increment();
} while (!counter.overflowFlag);
}
}
answered Dec 15 at 16:30
GuiRitter
222210
222210
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53780951%2fhow-to-get-all-possible-combinations-from-two-arrays-in-java%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
So the operators is limited, only 3?
– ZhaoGang
Dec 14 at 13:54
@ZhaoGang Yes, I have only 3 operators.
– Oleg Caralanski
Dec 14 at 13:58