Generating all weak orders

In a group decision making paper I am working on, one stage of the experimentation required the generation of weak orders.  I came across a nice way of generating complete orders (solution by tennenrishin), which I had needed to do before, however partial orderings seemed a bit harder, especially trying to generate all orders for any given set of objects.  My solution ended up building it from binary sets and, although it requires a checking function, I think in the end it’s quite succinct.

Generate all weak orders from input n

 weak.orders <- function(n) {
all.bins <- list()
for(j in 2:n) {
	bin.list <- array(0,0)
	for(i in 1:(2^j-2)) {
bin.list <- rbind(bin.list,as.numeric(intToBits(i))[1:j]) }
	all.bins[[j]] <- bin.list}

weak.orders <- rbind(array(0,n),all.bins[[n]])
	
for(l in 1:(n-1)) {
nwo <- nrow(weak.orders)
for(j in 2:(n-1)) {
bin.2add <- all.bins[[j]]
for(i in 1:nwo) {
if(sum(weak.orders[i,weak.orders[i,]==l])==l*j) {
for(k in 1:(nrow(bin.2add))) {
add.this <- weak.orders[i,]
add.this[add.this==l]<-add.this[add.this==l]+bin.2add[k,]
weak.orders <- rbind(weak.orders,add.this)}
}}}
}
weak.orders} 
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s