I have been trying to work this out for the past few days, and have not gotten very far.

Assume there are N objects and N places to put them in (N_{1} to N_{N}) and each place has M objects to choose from, however, each object may only appear once in the final "string" and a object may be in multiple places' sets.

To make it clearer I will provide an example.

Suppose we have 4 objects (1 through 4) and we will then have 4 places to put them into (A through D) and the following is true:

A={1}

B={2,3}

C={2,4}

D={2,3,4}

The number of combinations is 3:

1243

1324

1342

1242 cannot be as is uses object 2 twice

1234 cannot be because C cannot use object 3

I have tried so many solutions, but all of them don't work. Any help will be greatly appreciated.

Assume there are N objects and N places to put them in (N

To make it clearer I will provide an example.

Suppose we have 4 objects (1 through 4) and we will then have 4 places to put them into (A through D) and the following is true:

A={1}

B={2,3}

C={2,4}

D={2,3,4}

The number of combinations is 3:

1243

1324

1342

1242 cannot be as is uses object 2 twice

1234 cannot be because C cannot use object 3

I have tried so many solutions, but all of them don't work. Any help will be greatly appreciated.

@abhishekm71

No, I do not think you understand the question. Or I do not understand your answer.

@ne555

I have no idea how that relates, but I will do some more research and get back to you if I do not find anything.

Thank you both for your help thus far.

No, I do not think you understand the question. Or I do not understand your answer.

@ne555

I have no idea how that relates, but I will do some more research and get back to you if I do not find anything.

Thank you both for your help thus far.

You've got elements and positions as nodes

There is an edge between an element and a position if it can be put there

You want to count the number of perfect (using all the nodes) matching in the graph

There is an edge between an element and a position if it can be put there

You want to count the number of perfect (using all the nodes) matching in the graph

Last edited on

Ah, now I understand, however the understanding has raised a question or two:

1) Is the graph definitely planar, because if it is not, then the algorithm won't work?

2) Does anyone know a good tutorial on computational complexity, I know the basics, but have no idea what #P is, and wikipedia's definition did little to help that.

1) Is the graph definitely planar, because if it is not, then the algorithm won't work?

2) Does anyone know a good tutorial on computational complexity, I know the basics, but have no idea what #P is, and wikipedia's definition did little to help that.

Graphs are not inherently geometrical. |

Would you mind explaining, what you mean by that, and in reference to what did you say that, please?

Is the graph definitely planar |

Script Coder wrote: |
---|

@abhishekm71 No, I do not think you understand the question. Or I do not understand your answer. |

Yes I think I am failing to understand your question.

What I meant was, with N <= 1000 and M < 1000, there can be a case where N = 999 and for each prospective "place" (a

a

a

.

.

.

a

The number of combinations in this case shall be factorial (999).

Missing something?

What you are missing is that each pigeon hole can only hold a subset of the list of items.

What you are missing is that each pigeon hole can only hold a subset of the list of items. |

Actually I assumed that a list can be a subset of itself. However, even if you discard that assumption, then say in the example the OP gave, we can have:

A={1}

B={2,3,4}

C={2,3,4}

D={2,3,4}

The combinations are:

1234

1243

1324

1342

1423

1432

The number of combinations is factorial(3).

Similarly, if N = 1000 (not 999), then we can have a case where:

a

a

a

.

.

a

The number of combinations shall be factorial(999).

I'm sorry for my repeat question but I genuinely do not get where I am going wrong.

@abhishekm71 Yes it is possible to have those situations, it is not always the case, and therefore cannot be a general solution.

@helios I think you should read this: http://en.wikipedia.org/wiki/Planar_graph

Would the FKT algorithm work?

@helios I think you should read this: http://en.wikipedia.org/wiki/Planar_graph

Would the FKT algorithm work?

That is not the example the OP gave.

For his example, only three combinations are possible:

1 2 4 3

1 3 2 4

1 3 4 2

You are generalizing on a subproblem.

For his example, only three combinations are possible:

1 2 4 3

1 3 2 4

1 3 4 2

You are generalizing on a subproblem.

@Script Coder

My objective was not to give you the solution, but to give you an idea of the size of data involved with the bounds you are considering.

My objective was not to give you the solution, but to give you an idea of the size of data involved with the bounds you are considering.

@abhishekm71 Yes I know, that is why the original problem asked for a modulo 10 007 (In case you are worried about integer overflow) I did not think it would be necessary to add as all I want to know it the general algorithm for solving this type fro problem.

But anyway back on topic, would the FKT algorithm work?

But anyway back on topic, would the FKT algorithm work?

Topic archived. No new replies allowed.