Forum

> > CS2D > Scripts > [Math]Combination of words
ForenübersichtCS2D-Übersicht Scripts-ÜbersichtEinloggen, um zu antworten

Englisch [Math]Combination of words

26 Antworten
Seite
Zum Anfang Vorherige 1 2 Nächste Zum Anfang

verschoben [Math]Combination of words

KenVo
User Off Offline

Zitieren
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)

alt Re: [Math]Combination of words

BlazingStan
User Off Offline

Zitieren
Erhm...
You mean,add 1 more combination so there was 10? Looks like a little dumby

Then,
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?
1× editiert, zuletzt 27.02.12 18:17:33

alt Re: [Math]Combination of words

BlazingStan
User Off Offline

Zitieren
user 244453211332112: 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,
1
Atk,Magic,HP,Defense (Atk,Magic,HP,Defense,Atk + Magic,Atk + HP,Atk + Defense,Magic + HP,Magic + Defense,HP + Defense.)

But,its wrong.
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
1× editiert, zuletzt 28.02.12 00:01:15

alt Re: [Math]Combination of words

EngiN33R
Moderator Off Offline

Zitieren
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:

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

alt Re: [Math]Combination of words

BlazingStan
User Off Offline

Zitieren
user EngiN33R hat geschrieben
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:

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?

alt Re: [Math]Combination of words

DarkLight66
User Off Offline

Zitieren
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.

alt Re: [Math]Combination of words

EngiN33R
Moderator Off Offline

Zitieren
@user 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.

alt Re: [Math]Combination of words

Lee
Moderator Off Offline

Zitieren
So given the following definition of 'choosing' as

IMG:https://www.texify.com/img/%5CLARGE%5C%21%5Cleft%28%20n%20%5C%5C%20c%20%5Cright%29%20%3D%20%5Cfrac%7Bn%21%7D%7B%28n-c%29%21c%21%7D%20%3D%20%5Cprod_%7Bi%3D0%7D%5E%7Bc-1%7D%5Cfrac%7Bn-i%7D%7Bc-i%7D.gif


where order matters (so 'abc' is classified the same as 'bac'), then there are IMG:https://www.texify.com/img/%5CLARGE%5C%21%5Csum_%7Bi%3D1%7D%5E%7Bn%7D%20%5Cleft%28%20n%20%5C%5C%20i%20%5Cright%29.gif
different combinations.

For the n=10 case, there are 1023 different combinations.

alt Re: [Math]Combination of words

Lee
Moderator Off Offline

Zitieren
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)

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

using your test 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.

alt Re: [Math]Combination of words

KenVo
User Off Offline

Zitieren
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:
@user BlazingStan:
Zitat
He just cant explain the question.

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

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

@user 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.

@user Anders4000: Same as aboves
12× editiert, zuletzt 28.02.12 03:08:24

alt Re: [Math]Combination of words

Lee
Moderator Off Offline

Zitieren
For the 4 case, we have the following possible combinations:

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

ab
ac
ad
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).

Try 2^n - 1 instead as your formula.

alt Re: [Math]Combination of words

KenVo
User Off Offline

Zitieren
user Lee hat geschrieben
For the 4 case, we have the following possible combinations:

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

ab
ac
ad
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).

Try 2^n - 1 instead as your formula.


Yes, I just realized that after i posted it
1× editiert, zuletzt 28.02.12 03:10:24

alt Re: [Math]Combination of words

Flacko
User Off Offline

Zitieren
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.

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

alt Re: [Math]Combination of words

KenVo
User Off Offline

Zitieren
@user 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
2× editiert, zuletzt 28.02.12 05:07:10
Zum Anfang Vorherige 1 2 Nächste Zum Anfang
Einloggen, um zu antworten Scripts-ÜbersichtCS2D-ÜbersichtForenübersicht