brezniczky · July 16, 2016 14:33
diff --git a/is_it_ordered.R b/is_it_ordered.R
 # This code exhibits a vectorized function telling whether a series of numbers
 # is possibly sorted according to some (not necessarily increasing or
 # decreasing) order.
 #
 # "Possibly" as in practice a random unsorted series may not contradict being
 # sorted - e.g. 1, 3, 3, 2, 2 could be just a random discrete uniform sample.
 #
 # E.g. (1, 2, 5, 7, 7, 3, 3, 3, 8, 10, 10) is possibly sorted, but
 #      (1, 3, 2, 5, 2) cannot be, as 2 occurs in a disjoint way, separated by 5.

 is.ordered.sequence = function(x) {
  # Verifies if a sequence of numbers is possibly sorted in an arbitrary order.
  # The criteria is that equal values must be adjacent in x.
  #
  # Args:
  # x: vector containing the sequence of numbers to test, NA elements are not
  #    allowed (so impute as necessary).

  if (!is.vector(x)) {
    stop("x must be a vector")
  }

  if (length(x) == 0) {
    return(TRUE)
  }

  # create (x[n], x[n + 1]) pairs representing  state transitions from one value
  # to another, ignore the last element for now
  transitions = cbind(x[-length(x)], x[-1])

  # add the ignored last element with a unique "next", NA in this code
  if ((length(x) > 1) && (x[length(x)] != x[length(x) - 1])) {
    transitions = rbind(transitions, c(x[length(x)], NA))
  }

  if (is.vector(transitions)) {
    # it was a 1-element series == sorted!
    return(TRUE)
  }

  # leave only the first index of those pairs where there is a change
  # (i.e. x[i] != x[j])
  included = transitions[, 1] != transitions[, 2]
  included[is.na(included)] = TRUE

  transitions = transitions[included, ]

  # if any of the sources appear with a multiplicity, x could not be ordered
  count.transitions = length(transitions[, 1])
  count.sources = length(unique(transitions[, 1]))

  return(count.transitions == count.sources)
 }
	# This code exhibits a vectorized function telling whether a series of numbers
	# is possibly sorted according to some (not necessarily increasing or
	# decreasing) order.
	#
	# "Possibly" as in practice a random unsorted series may not contradict being
	# sorted - e.g. 1, 3, 3, 2, 2 could be just a random discrete uniform sample.
	#
	# E.g. (1, 2, 5, 7, 7, 3, 3, 3, 8, 10, 10) is possibly sorted, but
	# (1, 3, 2, 5, 2) cannot be, as 2 occurs in a disjoint way, separated by 5.

	is.ordered.sequence = function(x) {
	# Verifies if a sequence of numbers is possibly sorted in an arbitrary order.
	# The criteria is that equal values must be adjacent in x.
	#
	# Args:
	# x: vector containing the sequence of numbers to test, NA elements are not
	# allowed (so impute as necessary).

	if (!is.vector(x)) {
	stop("x must be a vector")
	}

	if (length(x) == 0) {
	return(TRUE)
	}

	# create (x[n], x[n + 1]) pairs representing state transitions from one value
	# to another, ignore the last element for now
	transitions = cbind(x[-length(x)], x[-1])

	# add the ignored last element with a unique "next", NA in this code
	if ((length(x) > 1) && (x[length(x)] != x[length(x) - 1])) {
	transitions = rbind(transitions, c(x[length(x)], NA))
	}

	if (is.vector(transitions)) {
	# it was a 1-element series == sorted!
	return(TRUE)
	}

	# leave only the first index of those pairs where there is a change
	# (i.e. x[i] != x[j])
	included = transitions[, 1] != transitions[, 2]
	included[is.na(included)] = TRUE

	transitions = transitions[included, ]

	# if any of the sources appear with a multiplicity, x could not be ordered
	count.transitions = length(transitions[, 1])
	count.sources = length(unique(transitions[, 1]))

	return(count.transitions == count.sources)
	}