Neo4j All permutations where node type is distinct in each

Question

What I'm trying to do is generate all the permutations of a collection of nodes but where each node type only appears once per permutation.

For example if I have a graph of u:User, l:Location, d:Device nodes, lets say 3 nodes of each type.

What I want to be able to generate is a collection that might look something like this

User ID: 1, Location ID: 1
User ID: 1, Location ID: 2
User ID: 1, Location ID: 3
User ID: 1, Device ID: 1
User ID: 1, Device ID: 2
User ID: 1, Device ID: 3
User ID: 1, Location ID: 1, Device ID: 1
User ID: 1, Location ID: 1, Device ID: 2
User ID: 1, Location ID: 1, Device ID: 3
User ID: 1, Location ID: 2, Device ID: 1
User ID: 1, Location ID: 2, Device ID: 2
User ID: 1, Location ID: 2, Device ID: 3

And so on, until I have all combinations.

What I don't want to happen is for a valid combination to include any of the node types more than once, so a combination can only have one user, one location and one device.

At the moment I'm using apoc.coll.combinations, but I don't seem to be able to work out a way to stop it from making the node type distinct.

If I were to run

MATCH (l:Location)-[]-(d:Device)-[]-(ur:User)
WITH COLLECT({l:l,ur:ur}) as coll
WITH apoc.coll.combinations(coll,1,size(coll)) as combColl
RETURN combColl

I'd run out of memory because valid combos would be all the locations and all the user risks.

Answer 1

You need to get one item combination per location, device and user using apoc.coll.combinations. Then do UNWIND to combine each of the items. The result is 3X3+3X3+3x3 + 3X3x3 = 54 rows

MATCH (l:Location)
MATCH (d:Device)
MATCH (u:User)
WITH  collect(l) as locations, collect(d) as devices, collect(u) as users
WITH apoc.coll.combinations(locations,1,1) as locations,  apoc.coll.combinations(devices,1,1) as devices, apoc.coll.combinations(users,1,1) as users 
UNWIND locations as location
UNWIND devices as device
UNWIND users as user
CALL {
       WITH location, device 
       RETURN collect(distinct  location+device) as cols 
       
       UNION ALL

       WITH location, user
       RETURN collect(distinct  location+user) as cols 
       
       UNION ALL
       
       WITH device, user
       RETURN collect(distinct  device+user) as cols
       
       UNION ALL
       
       WITH location, device, user
       RETURN collect(distinct  location+device+user) as cols
}
RETURN collect(distinct cols) as combColl

Result when I unwind the final collection:

╒══════════════════════════════╕
│"combColl"                    │
╞══════════════════════════════╡
│[[{"ID":1},{"ID":1}]]         │
├──────────────────────────────┤
│[[{"ID":1},{"ID":2}]]         │
├──────────────────────────────┤
│[[{"ID":1},{"ID":3}]]         │


....

├──────────────────────────────┤
│[[{"ID":3},{"ID":2},{"ID":3}]]│
├──────────────────────────────┤
│[[{"ID":3},{"ID":3},{"ID":1}]]│
├──────────────────────────────┤
│[[{"ID":3},{"ID":3},{"ID":2}]]│
├──────────────────────────────┤
│[[{"ID":3},{"ID":3},{"ID":3}]]│
└──────────────────────────────┘