• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 40,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

Conditional random cube state for given number of targets

sneze2r

Member
Joined
Nov 30, 2012
Messages
162
Location
Rumia, Poland
WCA
2012JALO01
YouTube
Visit Channel
Hello,

I have algebra problem. Suppose i want to generate random state on cube with given condition: there must be 14 targets for edges. Is there an `easy` aproach in implementation algoritm, that it will output vector of edges permutations which for given condition is properly distributed?

What do I want this for? I'm working on something like conditional scrambler, which for input conditions like "2 corners twisted+ one edge twisted+over 10 edge targets" will output me scramble satisfying these conditions and currently I'm only struggling with 'number of targets' module. I tried approach with some simple cycle breaking but It seems far to difficult. I can also simulate distribution of (targets.number x cycle.lengths.on.cube), and then on this empirical simulation result generate cycles on cube, but I expect that there is easier way to do this.
 

mark49152

Super Moderator
Staff member
Joined
Oct 29, 2012
Messages
4,703
Location
UK
WCA
2015RIVE05
YouTube
Visit Channel
It might not be the most elegant or efficient solution, but a simple way to avoid distorting the distribution would be to be generate random states then test them against the conditions and throw them away until you find one that matches.
 
Joined
Apr 23, 2010
Messages
1,391
Location
Scotland, UK
WCA
2009SHEE01
YouTube
Visit Channel
Seems to me like you would do something like:
-Choose whether buffer is solved (will affect other steps, will assume unsolved to simplify description)
-Have a list of all cycle structures for each number of targets (e.g. 10 = 8+2 = 7+3 = 6+4 = 6+2+2 etc.)
-Pick one of these randomly (weighted some way if you want)
-Go through each cycle, I guess starting with a random one including the buffer, and pick the targets at random making sure you keep track of which pieces have already been used. Remember you can have an even number of twisted cycles.

Shouldn't be too difficult to do, I'd give it a go myself but I don't know any relevant programming languages (and I don't have the time).
 

sneze2r

Member
Joined
Nov 30, 2012
Messages
162
Location
Rumia, Poland
WCA
2012JALO01
YouTube
Visit Channel
@mark49152 It is ok when You choose a case that occurs often like 12 edge targets. Buf for condition like 2 edges twisted+ 13 edge targets it migth be slow.

...
-Have a list of all cycle structures for each number of targets (e.g. 10 = 8+2 = 7+3 = 6+4 = 6+2+2 etc.)
-Pick one of these randomly (weighted some way if you want)
...
that's exactly what I will do i guess, since i have similar idea. But these weight's are important and i will have to estimate these and i did it for N=1000000. For instance, there are weights of cycles combination for condition :10 edge targets
upload_2017-5-12_23-36-48.png
'11' means cycle with length of 11 not including buffer, because 11>10. '9' means cycle with length of 9 that include buffer because 9<11(when buffer is solved, target number=+2) and 2,3,4 mean 3 separate cycles where neither of these contains buffer because 2+3+4<10 etc..... With this I'am able to do this, just pick one of these cases and apply egde permutation vector.
 

mark49152

Super Moderator
Staff member
Joined
Oct 29, 2012
Messages
4,703
Location
UK
WCA
2015RIVE05
YouTube
Visit Channel
@mark49152 It is ok when You choose a case that occurs often like 12 edge targets. Buf for condition like 2 edges twisted+ 13 edge targets it migth be slow.
Well it depends what you mean by slow - I'm no mathematician but I think for the worst cases you'd have to check tens of thousands of candidates, not billions, so within the range that a computer could do in a practically reasonable time.

Anyway, you are correct that it isn't efficient, and probably not as much fun either. Just easier :)
 

xyzzy

Member
Joined
Dec 24, 2015
Messages
2,355
Well it depends what you mean by slow - I'm no mathematician but I think for the worst cases you'd have to check tens of thousands of candidates, not billions, so within the range that a computer could do in a practically reasonable time.

Minor caveat: the actual worst case is really, really bad with this algorithm. To filter to no targets at all (i.e. a solved cube), you'd need to go through 43 quintillion states on average. For anything reasonable though, this ought to be pretty fast. (A computer can churn out a million random states per second! Checking that they meet the required criteria is easy too.)
 

mark49152

Super Moderator
Staff member
Joined
Oct 29, 2012
Messages
4,703
Location
UK
WCA
2015RIVE05
YouTube
Visit Channel
Minor caveat: the actual worst case is really, really bad with this algorithm. To filter to no targets at all (i.e. a solved cube), you'd need to go through 43 quintillion states on average.
That could be solved by fixing the solved and flipped pieces first and using iterative randomisation/checking only for the cycle pieces (the sole point being to avoid having to figure out relative probabilities of different combinations of cycle lengths). Likewise I'd handle edges and corners separately, so as to not throw out good edge distributions when corners are wrong, and vice versa.

I think the worst case would be six 2-cycles of edges and four 2-cycles of corners.
 

xyzzy

Member
Joined
Dec 24, 2015
Messages
2,355
That could be solved by fixing the solved and flipped pieces first and using iterative randomisation/checking only for the cycle pieces (the sole point being to avoid having to figure out relative probabilities of different combinations of cycle lengths).

Again, there's a caveat. Having n targets doesn't force the number of solved/flipped/twisted pieces to be fixed (unless you use arbitrary buffers), so if you set a fixed number of solved/flipped/twisted pieces at the start, you won't get the correct distribution.

And yeah, good point on generating the edges and corners separately. I initially thought there'd be some parity constraint making them nonseparable, but that's covered by the parity of the number of targets.
 

mark49152

Super Moderator
Staff member
Joined
Oct 29, 2012
Messages
4,703
Location
UK
WCA
2015RIVE05
YouTube
Visit Channel
Having n targets doesn't force the number of solved/flipped/twisted pieces to be fixed (unless you use arbitrary buffers), so if you set a fixed number of solved/flipped/twisted pieces at the start, you won't get the correct distribution.
If the desired number of flips/twists is left unspecified, true, but...

I'm working on something like conditional scrambler, which for input conditions like "2 corners twisted+ one edge twisted+over 10 edge targets" will output me scramble satisfying these conditions
In which case you could fix the twisted pieces at the start, but would then need to make sure that during the generation of random state distributions you do not add any additional twists otherwise you invalidate the specified counts.
 

SciTech

Member
Joined
Oct 21, 2017
Messages
7
As below. Written in the language R which you can regard as pseudo-code, but it is runnable; download R software (search for CRAN) and just copy and paste. Uses cycles and not targets because the number of targets depends on where your buffer is. Probably contains lots of bugs.

# Function for Rubik's cube sim with given cycles

# nEs = number of solved edges
# nEt = number of twisted edges
# nEcyc = vector of cycle lengths

# nCs = number of solved corners
# nCt = number of twisted corners (either clockwise or anti-clockwise)
# nCcyc = vector of cycle lengths

# Usage example:
# cubeSim(nEs=0, nEt=2, nEcyc=c(3,3,4), nCs=1, nCt=2, nCcyc=c(2,3))
# Output:
#$EP
# [1] 1 10 12 4 11 9 6 3 7 5 2 8
#$EO
# [1] 1 0 0 1 0 1 0 1 1 0 0 1
#$CP
# [1] 1 6 7 4 2 5 3 8
#$CO
# [1] 0 0 2 2 1 1 1 2

cubeSim <- function(nEs, nEt, nEcyc, nCs, nCt, nCcyc)
{
# Bulletproofing
if((length(nEcyc) == 1 && nEcyc == 0) || (length(nCcyc) == 1 && nCcyc == 0))
stop("to specify no cycles use the empty vector numeric(0)")
if(any(nEcyc < 2) || any(nCcyc < 2)) stop("cycles must have length two or above")
if(sum(nEcyc) + nEs + nEt != 12) stop("must have 12 edges")
if(sum(nCcyc) + nCs + nCt != 8) stop("must have 8 corners")

# Unsolvable if there are an odd number of even cycles for edges and corners combined
# In place (solved/twisted) pieces are odd (length one) cycles and so do not contribute
if((sum(c(nEcyc,nCcyc) %% 2 == 0) %% 2) == 1) stop("unsolvable due to permutation parity")

# Solved, twisted and remaining edges
Es <- sample(1:12, nEs)
Et <- sample(setdiff(1:12, Es), nEt)
Erem <- setdiff(1:12, c(Es,Et))

# Solved, twisted (clockwise or anticlockwise) and remaining corners
Cs <- sample(1:8, nCs)
Ct <- sample(setdiff(1:8, Cs), nCt)
Crem <- setdiff(1:8, c(Cs,Ct))

# Generate EP and EO
if(length(Erem) == 0) {
EP <- 1:12
EO <- rep(0,12); EO[Et] <- 1
if(sum(EO) %% 2 != 0) stop("unsolvable due to edge orientation")
} else if(length(Erem) == 1) {
EP <- 1:12
EO <- rep(0,12); EO[Et] <- 1
EO[Erem] <- -sum(EO) %% 2
} else {
cycle <- vector("list", length(nEcyc))
cycle[[1]] <- sample(Erem, nEcyc[1])
if(length(nEcyc) > 1) {
EremRd <- Erem
for(i in 2:length(nEcyc)) {
EremRd <- setdiff(EremRd, cycle[[i-1]])
cycle[] <- sample(EremRd, nEcyc)
}
}
EP <- 1:12
for(i in 1:length(nEcyc)) EP[cycle[]] <- c(cycle[][-1], cycle[][1])
EO <- rep(0,12); EO[Et] <- 1
EO[Erem[-1]] <- sample(0:1,length(Erem)-1,replace=TRUE)
EO[Erem[1]] <- -sum(EO) %% 2
}

# Generate CP and CO

if(length(Crem) == 0) {
CP <- 1:8
CO <- rep(0,8)
if(length(Ct) == 1) stop("unsolvable due to corner orientation")
if(length(Ct) > 1) {
# sample clockwise/anticlockwise twist
CO[Ct[-1]] <- sample(1:2,length(Ct)-1,replace=TRUE)
CO[Ct[1]] <- -sum(CO) %% 3
}
} else if(length(Crem) == 1) {
CP <- 1:8
CO <- rep(0,8)
# sample clockwise/anticlockwise twist
CO[Ct] <- sample(1:2,length(Ct),replace=TRUE)
CO[Crem] <- -sum(CO) %% 3
} else {
cycle <- vector("list", length(nCcyc))
cycle[[1]] <- sample(Crem, nCcyc[1])
if(length(nCcyc) > 1) {
CremRd <- Crem
for(i in 2:length(nCcyc)) {
CremRd <- setdiff(CremRd, cycle[[i-1]])
cycle[] <- sample(CremRd, nCcyc)
}
}
CP <- 1:8
for(i in 1:length(nCcyc)) CP[cycle[]] <- c(cycle[][-1], cycle[][1])
CO <- rep(0,8); CO[Ct] <- sample(1:2,length(Ct),replace=TRUE)
CO[Crem[-1]] <- sample(0:2,length(Crem)-1,replace=TRUE)
CO[Crem[1]] <- -sum(CO) %% 3
}
# Final Cube
list(EP=EP,EO=EO,CP=CP,CO=CO)
}
 

SciTech

Member
Joined
Oct 21, 2017
Messages
7
Formatting issue; all the cycle[ ] terms shoud be cycle[ [ i ] ]. Something weird happened to those.
 

SciTech

Member
Joined
Oct 21, 2017
Messages
7
One more. This only requires the number of cycles as an input, and not the length of each cycle.
Fortunately this still fixes the permutation sign. The number of targets is given in the preamble.

The hard part is to generate the cycle lengths to ensure each conditional state is equally likely.
For 2 or 3 cubies not in-place there can only be one cycle. For 4 or 5 there are up to two. And so on.
So I have a look-up object containing 1+1+2+2+..+5+5+6=36 different lookup tables for each possible combination.

Each table contains all the possible integer partitions (possible lengths of each cycle), and the total number of permutations with this permutation type. These frequencies can then be used to sample the cycle lengths using the correct weighting.

The code below is not runnable because the look-up object is not given, but you should be able to construct it.
If anyone really wants to run it I can send them the code to construct the look-up object offline.


# Function for Rubik's cube sim with given number of targets

# nEs = number of solved edges
# nEt = number of twisted edges
# nEcyc = number of edge cycles

# nCs = number of solved corners
# nCt = number of twisted corners (either clockwise or anti-clockwise)
# nCcyc = number of corner cycles

# the permutation sign (odd or even) is given by the sign of nXs+nXt+nXcyc
# the signs of nEs+nEt+nEcyc and nCs+nCt+nCcyc must be the same or the cube will not be solvable
# the number of targets is odd or even according to the permutation sign
# for odd-odd you have a parity issue, for even-even there is no parity issue

# the number of targets is almost always equal to 10+nEt-nEs+nEcyc for edges and 6+nCt-nCs+nCcyc for corners
# i believe there are only two exceptions as below
# (a) if your buffer contains a solved piece; this increases the targets by 2 (because if your buffer was somewhere else you would not need to deal with it)
# (b) if the number of cycles is zero; this increases the targets by 2 (because the minus 2 term derives from the first cycle, which would not exist here)

# Usage example:
# cubeSim(nEs=0, nEt=2, nEcyc=3, nCs=1, nCt=2, nCcyc=2)
# Output:
#$EP
#[1] 4 10 8 1 12 3 7 6 9 11 5 2
#
#$EO
#[1] 1 0 1 1 0 1 1 1 1 0 1 0
#
#$CP
#[1] 3 2 1 8 5 4 7 6
#
#$CO
#[1] 2 0 1 1 1 2 2 0
#
cubeSim <- function(nEs, nEt, nEcyc, nCs, nCt, nCcyc)
{
# Bulletproofing
if(nEs + nEt > 12) stop("cannot have more than 12 edges")
if(nCs + nCt > 8) stop("cannot have more than 8 corners")
if(2*nEcyc > (12 - nEs - nEt)) stop("too many cycles for not enough cubies")
if((nEcyc == 0) && ((nEs + nEt) != 12)) stop("for zero cycles number of in-place edges must be 12")
if((nCcyc == 0) && ((nCs + nCt) != 8)) stop("for zero cycles number of in-place corners must be 8")
if(((nEs+nEt+nEcyc+nCs+nCt+nCcyc) %% 2) == 1) stop("unsolvable due to permutation parity")

# Solved, twisted and remaining edges
Es <- sample(1:12, nEs)
Et <- sample(setdiff(1:12, Es), nEt)
Erem <- setdiff(1:12, c(Es,Et))

# Solved, twisted (clockwise or anticlockwise) and remaining corners
Cs <- sample(1:8, nCs)
Ct <- sample(setdiff(1:8, Cs), nCt)
Crem <- setdiff(1:8, c(Cs,Ct))

# Generate EP and EO
nErem <- length(Erem)
if(nErem == 0) {
EP <- 1:12
EO <- rep(0,12); EO[Et] <- 1
if(sum(EO) %% 2 != 0) stop("unsolvable due to edge orientation")
} else if(nErem == 1) {
stop("code error: this should not occur due to bulletproofing")
} else {
# generate vector of edge cycle lengths nEcycVec using partproblu lookup object
obj <- partproblu[[nErem]][[nEcyc]]
indx <- sample.int(length(obj$freq), size = 1, prob = obj$freq)
nEcycVec <- obj$cyclen[,indx]
# generate EP
cycle <- vector("list", length(nEcycVec))
cycle[[1]] <- sample(Erem, nEcycVec[1])
if(length(nEcycVec) > 1) {
EremRd <- Erem
for(k in 2:length(nEcycVec)) {
EremRd <- setdiff(EremRd, cycle[[k-1]])
cycle[[k]] <- sample(EremRd, nEcycVec[k])
}
}
EP <- 1:12
for(k in 1:length(nEcycVec)) EP[cycle[[k]]] <- c(cycle[[k]][-1], cycle[[k]][1])
EO <- rep(0,12); EO[Et] <- 1
EO[Erem[-1]] <- sample(0:1,length(Erem)-1,replace=TRUE)
EO[Erem[1]] <- -sum(EO) %% 2
}

# Generate CP and CO
nCrem <- length(Crem)
if(nCrem == 0) {
CP <- 1:8
CO <- rep(0,8)
if(length(Ct) == 1) stop("unsolvable due to corner orientation")
if(length(Ct) > 1) {
# sample clockwise/anticlockwise twist
CO[Ct[-1]] <- sample(1:2,length(Ct)-1,replace=TRUE)
CO[Ct[1]] <- -sum(CO) %% 3
}
} else if(nCrem == 1) {
stop("code error: this should not occur due to bulletproofing")
} else {
# generate vector of corner cycle lengths nCcycVec using partproblu lookup object
obj <- partproblu[[nCrem]][[nCcyc]]
indx <- sample.int(length(obj$freq), size = 1, prob = obj$freq)
nCcycVec <- obj$cyclen[,indx]
# generate EP
cycle <- vector("list", length(nCcycVec))
cycle[[1]] <- sample(Crem, nCcycVec[1])
if(length(nCcycVec) > 1) {
CremRd <- Crem
for(k in 2:length(nCcycVec)) {
CremRd <- setdiff(CremRd, cycle[[k-1]])
cycle[[k]] <- sample(CremRd, nCcycVec[k])
}
}
CP <- 1:8
for(k in 1:length(nCcycVec)) CP[cycle[[k]]] <- c(cycle[[k]][-1], cycle[[k]][1])
CO <- rep(0,8); CO[Ct] <- sample(1:2,length(Ct),replace=TRUE)
CO[Crem[-1]] <- sample(0:2,length(Crem)-1,replace=TRUE)
CO[Crem[1]] <- -sum(CO) %% 3
}
# Final Cube
list(EP=EP,EO=EO,CP=CP,CO=CO)
}
 
Top