Every combination of elements in a 2-D array

[Owain]

Hello, I am writting a chatbot which works out a percetage match based on human reading style of a search term and the input. For flexibility, parts of the search term can vary, for example if this was used:

<hello,hey> there! Having a nice <morning,afternoon>?

Then the function would test all of these strings, and return the best match:

hello there! Having a nice morning?
hello there! Having a nice afternoon?
hey there! Having a nice morning?
hey there! Having a nice afternoon?

The code creates a 16x16 2-D array to store all the terms in, with unused spaces just containing an empty string:

                   GROUPS (<...> = group)
           0          1          2          3          4...
         0 "hello"     "morning" ""         ""         ""

TERMS
         1 "hey"       "afternoon"""        ""         ""
         .
         .
         .

However, I cant figure out a way to test every single possibilty of combinations that one of these 'flexable terms' could yeild. The only thing I thought of would be making a 16-deep nested for loop, which seems monstrous. Although that may be the only soloution, I dont know. My question is, is there a better way of doing this? Or is the evil for loops the only option. Thankyou

P.S If its relevent, my code also creates a 32 element array containg the positions of the main string which needs to be replaced by the terms. e.g:

<hello,hey> there! Having a nice <morning,afternoon>?
^         ^                      ^                 ^
0         13                     44                61

foo[0] = 0
foo[1] = 13
foo[2] = 44
foo[3] = 61
foo[4] = -1
foo[5] = -1
etc...

[BlackSheep]

Since your data set is so small you could always use pairs (or triplets) of data.

Let's say you have 4 groups of two. A 4-deep loop would take 16 cycles.
Instead, combine the first two groups (4 cycles), combine the last two groups (4 cycles), and then loop through those (2*2 = 4). Total is only 12 cycles.

EDIT: Never mind the above. I'm a little tired... If you want every combination, then going through every combination is unavoidable XD You might be able to speed it up using efficient caching though. Or even better, write an algorithm that can predict which combinations will be the highest scoring.

[whitenite1]

@Owain

The problem you described, seemed interesting, so I came up with this solution. It does most of what you wrote about, but you'll have to ramp it up to what you fully need. Hope it helps.

// Element Combinations.cpp : main project file.
#include <stdafx.h> // Used with Visual C++. Remove if not needed
#include <conio.h>
#include <iostream>
#include <string>

using namespace std;

void Print_Elements(string);
void WaitKey();

int main(int)
{
	string sentence;

	cout << "\tPlease enter the combination sentence as " << endl;
	cout << "Beginning <words> connecting part of sentence <words> and ending." << endl << "You may have have up to 6 words between each set of < >, separated by commas." << endl;
	getline(cin,sentence);
	Print_Elements(sentence);
	WaitKey();
	return 0;
}

void Print_Elements(string words)
{
	int start1 = 1, start2 = 1;
	int len, x, y, z, foo[4];
	z=0;
	len = words.length();
	string group1[6], group2[6], connecting[3] = {"","",""};
	for (int ck = 0; ck < len; ck++)
	{
		if( words[ck] == '<' || words[ck] == '>')
		{
			foo[z] = ck;
			z++;
		}
	}

	if (z == 4)
	{

		for ( int ck = 0; ck<4; ck++)
			cout << words[foo[ck]] << " is located at position " << foo[ck] << " in the sentence." << endl << endl;

		for (int ck = 0; ck < foo[0]; ck++)
		{
			connecting[0] = connecting[0] + words[ck] ;
		}
	
		for (int ck = foo[0]+1; ck < foo[1]; ck++)
		{
			if (words[ck] !=',')
				group1[start1-1] = group1[start1-1]+words[ck] ;
			if (words[ck] ==',')
				start1++;
		}
		
		for (int ck = foo[2]+1; ck < foo[3]; ck++)
		{
			if (words[ck] !=',')
				group2[start2-1] = group2[start2-1]+words[ck] ;
			if (words[ck] ==',')
				start2++;
		}

		for (int ck = foo[1]+1; ck < foo[2]; ck++)
		{
			connecting[1] = connecting[1] + words[ck] ;
		}

		if ( len > foo[3])
		{
			for (int ck = foo[3]+1; ck < len; ck++)
			{
				connecting[2] = connecting[2] + words[ck] ;
			}
		}


		for (x=0;x<start1;x++)
			for (y=0;y<start2;y++)
				cout << connecting[0] << group1[x] << connecting[1] << group2[y]<< connecting[2] << endl << endl;
	}
	if (z != 4)
		cout << endl << "Error detected in sentence. You do NOT have two sets of '< >'." << endl <<"\t\tPlease check input." << endl << endl;
}

void WaitKey()
{
cout << "\t\tPress ENTER to continue...\n\t\t";
while (_kbhit()) _getch(); // Empty the input buffer
_getch(); // Wait for a key
while (_kbhit()) _getch(); // Empty the input buffer (some keys sends two messages)
}

EDIT: Added to program to allow words before the first set of <>, and to have up to 6 words, separated by commas, between each set of < >..

[TheIdeasMan]

If you have a vector of ints, the next_permutation algorithm in a for loop will give you each different permutation. You could combine that with some logic to rearrange your strings.


Google all this, and read up about it.

HTH