# Forum

CS2D Scripts [Math]Combination of words

# [Math]Combination of words

26 replies
Goto Page
1 2
27.02.12 04:42:41 pm
KenVo
User
Offline
Can someone help me to solve this:
Atk - 1 combination
Atk, Magic - 3 combinations (Atk,Magic,Atk+Magic)
Atk, Magic, Hp - 7 combinations (Atk,Magic,Hp,Atk+Magic,Att+Hp,Magic+Hp,Atk+Magic+Hp)

I need to find the possible combination for 10 words. Note that you can't use the same word again in a combination( after you use Atk+Magic, you can't use Magic+Atk)
27.02.12 04:49:49 pm
MAX-russia
User
Offline
Its not possible really
27.02.12 04:52:54 pm
Alistaire
User
Offline
You're making it too difficult.
27.02.12 05:54:29 pm
Anders4000
User
Offline
I didn't even understand your question, be more specific.
27.02.12 06:14:09 pm
BlazingStan
User
Offline
Erhm...
You mean,add 1 more combination so there was 10? Looks like a little dumby

Then,
Code:
1
Atk,Magic,HP,Defense (Atk,Magic,HP,Defense,Atk + Magic,Atk + HP,Atk + Defense,Magic + HP,Magic + Defense,HP + Defense.)

Just add defense (or whatsoever),and thats all.

Here you are,10 words. Or you mean something another?..

[EDIT]
Also,is it for script?
edited 1×, last 27.02.12 06:17:33 pm
27.02.12 06:16:48 pm
Nexmann
User
Offline
This isn't working.
27.02.12 06:18:21 pm
BlazingStan
User
Offline
Nexmann: I am trying to help

He just cant explain the question.

[EDIT]
If Atk, Magic, Hp - 7 combinations (Atk,Magic,Hp,Atk+Magic,Att+Hp,Magic+Hp,Atk+Magic+Hp)

Then,its impossible to make 10 combinations.
As I said,
Code:
1
Atk,Magic,HP,Defense (Atk,Magic,HP,Defense,Atk + Magic,Atk + HP,Atk + Defense,Magic + HP,Magic + Defense,HP + Defense.)

But,its wrong.
Code:
1
Atk,Magic,HP,Defense (Atk,Magic,HP,Defense,Atk + Magic,Atk + HP,Atk + Defense,Magic + HP,Magic + Defense,HP + Defense,Atk+Magic+HP,Magic+HP+Defense,Atk+HP+Defense.)

That means,that you can get 1 - 3 - 7 - 13 combinations.

Or,am I again wrong?

Nah,Honestly,I am sucking at maths
edited 1×, last 28.02.12 12:01:15 am
27.02.12 09:45:30 pm
EngiN33R
Moderator
Offline
Err, I'm not sure if this will do what you want, but to find the amount of possible combinations of objects you'll have to use something called a factorial. If you have 4 objects: A, B, C, D, and you want to find out all possible combinations of those objects, that will be 4! = 24. But since you have it so that you can't do the same in reverse order, i.e. if AB was used BA cannot be used already, it's going to be more than that... I'm kind of useless when it comes to this, to be honest. The Lua factorial function though is as follows:

Code:
1
2
3
4
5
6
7
8
9
function math.factorial(n)
local x=n
local r=1
while x>0 do
r=r*x
x=x-1
end
return r
end
I code, therefore I exist. | Visit my blog for Lua tips and other interesting info
27.02.12 09:47:26 pm
BlazingStan
User
Offline
EngiN33R has written:
Err, I'm not sure if this will do what you want, but to find the amount of possible combinations of objects you'll have to use something called a factorial. If you have 4 objects: A, B, C, D, and you want to find out all possible combinations of those objects, that will be 4! = 24. But since you have it so that you can't do the same in reverse order, i.e. if AB was used BA cannot be used already, it's going to be more than that... I'm kind of useless when it comes to this, to be honest. The Lua factorial function though is as follows:

Code:
1
2
3
4
5
6
7
8
9
function math.factorial(n)
local x=n
local r=1
while x>0 do
r=r*x
x=x-1
end
return r
end

Looks like I've just broked my brains
In lua script it looks a little easier.

But,I wonder,what he wants from this?
27.02.12 09:49:40 pm
Alistaire
User
Offline
It's that he didn't state his question right..
27.02.12 09:50:26 pm
DarkLight66
User
Offline
Well , if you want to know how much of those combinations you can do, just use (2^x)-1, were x its the number of words you want to put. In case of being 10 words it would be (2^10)-1 = 1023 combinations. Of course, this wont give you the combinations, it just tells you how much you can get.

Edit: @enginer the factorial would work if he wanted all variations of words you can do caring about the order. But he want how much subsets can be made from the words, not caring about the order.
27.02.12 09:57:42 pm
EngiN33R
Moderator
Offline
@ DarkLight66: I may not understand you clearly, but he said that if there are three words, let them be denominated as A, B and C, the following combos can be made:

A,B,C,AB,AC,BC,ABC

So I guess he does care about the order.
I code, therefore I exist. | Visit my blog for Lua tips and other interesting info
27.02.12 11:55:41 pm
Lee
Moderator
Offline
So given the following definition of 'choosing' as

where order matters (so 'abc' is classified the same as 'bac'), then there are different combinations.

For the n=10 case, there are 1023 different combinations.
28.02.12 12:26:30 am
Flacko
User
Offline
IMHO it's pretty clear, he just wants a function that for a given set, returns all it's possible sub sets excluding the empty set.
Look on power sets.
Edit: here are two implementations in Lua: http://rosettacode.org/wiki/Power_set#Lua
edited 1×, last 28.02.12 01:30:50 am
28.02.12 01:30:18 am
Lee
Moderator
Offline
To generate this set, notice that if we define the subproblem of finding all combinations of a set of rank n, then

subproblem({1,2,3},2) = {1,2},{1,3},{2,3} = {1,2},{1,3}, subproblem({2,3},2)
subproblem({0,1,2,3},3) = {0,1,2},{0,1,3},{0,2,3}, subproblem({1,2,3},3)
= {0 + subproblem({1,2,3},2)}, subproblem({1,2,3},3)

subproblem(set, n) = {set[1] + subproblem(set[1:], n-1)}, subproblem(set[1:], n)

Code:
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
function subproblem(set, n)
-- base case is when n>#set
if n > #set then return {} end
if n == 1 then
local solution = {}
for _,v in ipairs(set) do
table.insert(solution, {v})
end
return solution
end

-- 1 + subproblem(set[1:],n-1)
local solution = {}
local next = {unpack(set)}
table.remove(next,1)
for _,v in ipairs(subproblem(next,n-1)) do
table.insert(solution, {set[1], unpack(v)})
end

next = {unpack(set)}
table.remove(next,1)
for _,v in ipairs(subproblem(next, n)) do
table.insert(solution,v)
end

return solution
end

function solve(set)
local solution = {}
for i=1,#set do
for _, item in ipairs(subproblem(set,i)) do
table.insert(solution,item)
end
end

return solution
end

Code:
1
2
> see(solve({'atk','magazine','hp'}))
{{atk}, {magazine}, {hp}, {atk, magazine}, {atk, hp}, {magazine, hp}, {atk, magazine, hp}}

You can optimize by noticing that subproblem's index increases monotonically, so if we cache certain indices, we can do this in O(n*n^2) time ~= a few thousand operations total.
28.02.12 02:02:57 am
KenVo
User
Offline
Lol, you guys are making it kinda too complicated (idk about other people but for me)

I'm sorry if my question wasn't clear, I was in a rush because I had to go to school.
BTW, Replies:
@ BlazingStan:
Quote:
He just cant explain the question.

Thanks for your helps, but I explained that to 3 of my friends and they all understood.

@ MAX-russia: Did you even try? And not possible?

@ Alistaire: What's your point? Same as my response to Blazer, I explained that to 3 of my friends and they all understood. Flacko also said that it was clear.

@ Anders4000: Same as aboves
edited 12×, last 28.02.12 03:08:24 am
28.02.12 02:55:13 am
Lee
Moderator
Offline
For the 4 case, we have the following possible combinations:

Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
a
b
c
d

ab
ac
bc
bd
cd

abc
abd
acd
bcd

abcd

This is already a contradiction to your formula as there are 15 different combinations in here in addition to null (equivalent to not choosing).

28.02.12 03:00:22 am
KenVo
User
Offline
Lee has written:
For the 4 case, we have the following possible combinations:

Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
a
b
c
d

ab
ac
bc
bd
cd

abc
abd
acd
bcd

abcd

This is already a contradiction to your formula as there are 15 different combinations in here in addition to null (equivalent to not choosing).

Yes, I just realized that after i posted it
edited 1×, last 28.02.12 03:10:24 am
28.02.12 04:10:37 am
Flacko
User
Offline
Anyways, Alistaire is still right. You have 1024 instaces of the same item with very very slight differences which is not efficient, plus, if you have like ten different items, you will have 10240 sub-types of these items.

Better to use prototyping instead. I don't really know if it's practical to implement in Tibia.

Code:
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
--Prototype for the item:
items =
{
[300] = {
name = "leather helmet",
desc = "Protect yourself from headshots!",
r = 128, g = 64, b = 0,
action = "equip",
slot = 1,
eimage = "gfx/weiwen/helmet.png",
fimage = "gfx/weiwen/helmet.png",
def = 0.05,
speed = -1,
func = equip,
}
}

prefix_num = 3
prefix_names = {"Hard","Light","Shiny"}
prefix_desc = {"+10% def", "+3 speed","Has a nice white color"}
prefix_stat = {
{10, "%", "def"},
{3, "+", "speed"},
{255, "=", "r,g,b"}
}

function generate_instance(prototype) --prototype should be 300 for this example
local t = table.copy(items[prototype])
local bonuses = {}
for i=1, math.random(0,prefix_num)  do
local newstat = math.random(1,prefix_num)
while bonuses[newstat] do
newstat = newstat%prefix_num+1
end
bonuses[newstat] = true
t.name = prefix_names[newstat] .. t.name
t.desc = t.desc .." ".. prefix_desc[newstat]
for k, v in pairs(string.split(prefix_stat[newstat][3],",")) do --for each variable separated by comma
local operator = prefix_stat[newstat][2]
local ammount = prefix_stat[newstat][1]
if operator  == "%" then
t[v] = t[v] + t[v]*ammount/100
elseif operator ==  "+" then
t[v] = t[v] + ammount
elseif operator == "=" then
t[v] = ammount
end
end
end
return t
end

--
--OUTPUT
--
local ins = generate_instance(300)

for k,v in pairs(ins) do
print(k..": "..v)
end
28.02.12 04:38:15 am
KenVo
User
Offline
@ Flacko: You are right. What I was going to do is make over 1000 tables for each items and save it to a file . I'll try your method.
But I think the problem is that it would gives the player random item bonuses every time he re-equip the item, which is...not what i wanted.
Ok so should I come up with this? I will limit the amount of possible bonuses, like you can only have an item with 3 maximum bonuses rather than 10 bonuses. That way would greatly decrease the amount of instances.

If I come up with that, there would be 175 combinations for each item.
I'm planning to make 120 items, 120x175 = 21000 Item IDs
Comparing to 1023 combinations of item's bonus: 122760
21000
122760

Big difference
edited 2×, last 28.02.12 05:07:10 am
1 2
﻿