permutation help

aarjm123 (8)
I am trying to generate two arrays from one big array, of which the sum of the 2 array's elements are as close to equal or equal to each other if possible, or one array summed up minus the second array summed up will be as close to zero as possible. I start with int array of 30.

It says that the lowest possible combination of one array minus the other is 239 which I know is not true. Also this needs to run in under ten minutes. Any help would be greatly appreciated.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
 
#include <iostream>
using namespace std;
const int size = 30;
int bestyet = 9999;
void swap(char *fir, char *sec)
{
	if (*fir == *sec)
		return;
	char temp = *fir;
	*fir = *sec;
	*sec = temp;
}
//the purpose of the find largest function is to save running time
int* findlargest(int arr[], int size,  int num)
{
	int* copy = new int[size];
	for (int w = 0; w < size; w++)
	{
		copy[w] = arr[w];
	}
	int* largest = new int[num];
	for (int z = 0; z < num; z++)
	{
		int largestsofar = -1, n = -1;
		for (int a = 0; a < size; a++)
		{
			if (copy[a]>largestsofar)
			{
				largestsofar = copy[a];
				n = a;
			}
		}
		copy[n] = -1;
		largest[z] = largestsofar;
	}
	delete copy;
	copy = NULL;
	return largest;
}
void permutation(int * arr, int curr, int size, char* plusorminus, int numofminuses)
{
	if (curr == size - 1)
	{
		int total = 0;
		for (int a = 0; a < size; a++)
		{
			if (plusorminus[a] == '-')
				total -= arr[a];
			if (plusorminus[a] == '+')
				total += arr[a];
		}
		if (total < 0)
			total *= -1;
		if (total == 0)
		{
			for (int n = 0; n < size; n++)
				cout << plusorminus[n] << arr[n] << " ";
			cout << "= " << total;
			cout << endl;
		}
		if (total < bestyet)
		{
			bestyet = total;
			for (int n = 0; n < size;n++)
				cout << plusorminus[n] << arr[n] << " ";
			cout << "= " << total;
			cout << endl;
		}
	}
	else
	{
		int idk = 0;
		for (int t = 0; t < size; t++)
		{
			idk += arr[t];
		}
		int* rand = new int[numofminuses];
		rand = findlargest(arr, size, numofminuses);
		for (int t = 0; t < numofminuses; t++)
		{
			idk -= (2 * (rand[t]));
		}
		delete rand;
		rand = NULL;
		if ((idk>0))
			return;
		for (int i = curr; i<size; i++)
		{
			swap(plusorminus[curr], plusorminus[i]);
			permutation(arr, curr + 1, size, plusorminus, numofminuses);
			swap(plusorminus[curr], plusorminus[i]);
		}
	}
}
int main()
{
	int num[size] = { 14, 9, 23, 5, 67, 19, 3, 2, 2, 4, 5, 3, 8, 3, 6, 56, 12, 14, 73, 9, 1, 13, 2, 15, 18, 21, 33, 35, 7, 1};
	char* c = new char[size];
	int x = size-1;
	while (x >= (size/2)-1)
	{
		int numofminuses = 0;
		for (int n = 0; n < size; n++)
		{
			c[n] = '+';
		}
		for (int n = x; n < size; n++)
		{
			c[n] = '-';
			numofminuses++;
		}
		permutation(num, 0, size, c, numofminuses);
		x--;
	}
	return 0;
}
closed account (48T7M4Gy)
A possible solution?

Sort the big array, get the total for that array, find the midpoint and split at that point to the 2 new arrays.

No permutations required. :)
aarjm123 (8)
The problem is that the arrays can be two different sizes so splitting them isn't necessarily going to produce the closest to equal arrays.
Smac89 (1727)
int num[size] = {14, 9, 23, 5, 67, 19, 3, 2, 2, 4, 5, 3, 8, 3, 6, 56, 12, 14, 73, 9, 1, 13, 2, 15, 18, 21, 33, 35, 7, 1};

sorted = 1, 1, 2, 2, 2, 3, 3, 3, 4, 5, 5, 6, 7, 8, 9, 9, 12, 13, 14, 14, 15, 18, 19, 21, 23, 33, 35, 56, 67, 73

Find the mean of the array:
16.1
Find the median:
9

Take the largest of the 2 and set it as your pivot point

split the array at the point where values are above the pivot and values are below the pivot and you get these 2 arrays:
[1, 1, 2, 2, 2, 3, 3, 3, 4, 5, 5, 6, 7, 8, 9, 9, 12, 13, 14, 14, 15] and [18, 19, 21, 23, 33, 35, 56, 67, 73]

Now you start the balancing act:
Get the sum of the 2 arrays and start swapping values to make their sums as close to equal as possible
Start with making the array with the larger sum as close as possible to the array with the smaller sum
If they are still not equal, and the smaller array is now larger try using values from that one to balance the other one. This should get them as close as possible to each other

EDIT:
Initial sum of both arrays:
138 and 345
After first balancing, I got
252 and 231
[1, 1, 2, 2, 2, 3, 3, 3, 4, 5, 5, 6, 7, 8, 9, 9, 12, 13, 14, 14, 15, 18, 19, 21, 23, 33] and [35, 56, 67, 73]
After second I get:
241 and 242
[3, 3, 4, 5, 5, 6, 7, 8, 9, 9, 12, 13, 14, 14, 15, 18, 19, 21, 23, 33] and [35, 56, 67, 73, 1, 1, 2, 2, 2, 3]

EDIT 2:
Note this method is not proven to work for other problems of this type, I even looked up this particular problem on Google and turns out it is NP-hard.
Last edited on
aarjm123 (8)
Thank you so much! That makes a lot of sense.
Topic archived. No new replies allowed.