R order vectors so that difference between most of the elements are positive

Question

I have two vectors

A = c(30709,28587,21672,20873,19877)

B = c(20213,21865,26217,30558,31674)

Vector B is always sorted in ascending order

I need to shuffle vector A in such a way that when taking difference (A-B), most of them should yield result +ve.

Here, output A needs to look like (20873,28587,30709,19877,21672) because this order will give me 3 differences(A-B) which will be +ve

there could be more than one combinations that can rresult in this case `c(20873, 19877, 28587, 30709, 21679) - B` also gives 3 positive. So, it is not clear which one you would pick — akrun, Apr 04 '20 at 15:46
I posted a solution with `permutations`. Please check if that helps — akrun, Apr 04 '20 at 16:00
It can be done but the `arrangements` is pretty fast and if we do with base, it would not be that efficient. the function is written in C — akrun, Apr 04 '20 at 16:32
See stackoverflow.com/questions/11095992/… or my edited post for base R functions. — user12728748, Apr 04 '20 at 18:10

user12728748 · Answer 1 · 2020-04-04T17:21:02.397

So many options for permutations... here is one using the Rfast package:

library(Rfast)
#> Loading required package: Rcpp
#> Loading required package: RcppZiggurat
A = c(30709,28587,21672,20873,19877)
B = c(20213,21865,26217,30558,31674)
pa <- permutation(A)
pA <- sapply(seq_len(dim(pa)[1]), function(x) pa[x,] - B)
pa[colSums(sign(pA)) == max(colSums(sign(pA))), ]
#>        [,1]  [,2]  [,3]  [,4]  [,5]
#>  [1,] 20873 19877 28587 30709 21672
#>  [2,] 20873 21672 28587 30709 19877
#>  [3,] 20873 28587 19877 30709 21672
#>  [4,] 20873 28587 21672 30709 19877
#>  [5,] 20873 28587 30709 19877 21672
#>  [6,] 20873 28587 30709 21672 19877
#>  [7,] 20873 30709 28587 19877 21672
#>  [8,] 20873 30709 28587 21672 19877
#>  [9,] 21672 19877 28587 30709 20873
#> [10,] 21672 20873 28587 30709 19877
#> [11,] 21672 28587 19877 30709 20873
#> [12,] 21672 28587 20873 30709 19877
#> [13,] 21672 28587 30709 19877 20873
#> [14,] 21672 28587 30709 20873 19877
#> [15,] 21672 30709 28587 19877 20873
#> [16,] 21672 30709 28587 20873 19877

Edit: base R version:

A = c(30709,28587,21672,20873,19877)
B = c(20213,21865,26217,30558,31674)

permutation <- function(x) {
    if (length(x) == 1) {
        return(x)
    }
    else {
        res <- matrix(nrow = 0, ncol = length(x))
        for (i in seq_along(x)) {
            res <- rbind(res, cbind(x[i], Recall(x[-i])))
        }
        return(res)
    }
}

pa <- permutation(A)
pA <- sapply(seq_len(dim(pa)[1]), function(x) pa[x,] - B)
pa[colSums(sign(pA)) == max(colSums(sign(pA))), ]
#>        [,1]  [,2]  [,3]  [,4]  [,5]
#>  [1,] 21672 30709 28587 20873 19877
#>  [2,] 21672 30709 28587 19877 20873
#>  [3,] 21672 28587 30709 20873 19877
#>  [4,] 21672 28587 30709 19877 20873
#>  [5,] 21672 28587 20873 30709 19877
#>  [6,] 21672 28587 19877 30709 20873
#>  [7,] 21672 20873 28587 30709 19877
#>  [8,] 21672 19877 28587 30709 20873
#>  [9,] 20873 30709 28587 21672 19877
#> [10,] 20873 30709 28587 19877 21672
#> [11,] 20873 28587 30709 21672 19877
#> [12,] 20873 28587 30709 19877 21672
#> [13,] 20873 28587 21672 30709 19877
#> [14,] 20873 28587 19877 30709 21672
#> [15,] 20873 21672 28587 30709 19877
#> [16,] 20873 19877 28587 30709 21672

^{Created on 2020-04-04 by the reprex package (v0.3.0)}

^{Reference: Generating all distinct permutations of a list in R}

Is there any way that it can be implemented without any packages ? — Gaurav Chavan, Apr 04 '20 at 16:57
@Gaurav Chavan: see https://stackoverflow.com/questions/11095992/generating-all-distinct-permutations-of-a-list-in-r for base R functions — user12728748, Apr 04 '20 at 17:00

score 1 · Answer 2 · answered Apr 04 '20 at 15:52

This solution could be computationally expensive if your vectors A and B have many elements, but in this case it's instantaneous.

# create a dataframe of all possible permutations of A
perms <- as.data.frame(gtools::permutations(length(A), length(A), A))
# add a column that will signal how many positive differences A-B there will be
perms$num_positives <- 0

# for each row in the dataframe, calculate how many positive differences A-B there are
for (i in 1:nrow(perms))
  perms$num_positives[i] <- sum(perms[i,] > B)

# order the dataframe according to the descending number of positive differences
perms[order(perms$num_positives, decreasing = TRUE), ]

Output

       V1    V2    V3    V4    V5 num_positives
28  20873 19877 28587 30709 21672             3
34  20873 21672 28587 30709 19877             3
38  20873 28587 19877 30709 21672             3
40  20873 28587 21672 30709 19877             3
41  20873 28587 30709 19877 21672             3
...

num_positives is the number of positive differences between A and B.

In your case there are many permutations of A that get a number of positive differences A-B equal to 3, as shown in the output.

score 1 · Answer 3 · answered Apr 04 '20 at 15:57

We can use permutations from arrangements to create all the permutation, then subtract it with 'B', get the rowSums of the difference greater than 0, and subset the 'm1' where the count is max, In this case, the max is 3 and these are the combinations that would create that max difference of positive values

library(arrangements)
m1 <- permutations(A, length(A)) 
c1 <-  rowSums(m1- B[col(m1)] > 0)
m1[c1 == max(c1),]
#     [,1]  [,2]  [,3]  [,4]  [,5]
# [1,] 21672 30709 28587 20873 19877
# [2,] 21672 30709 28587 19877 20873
# [3,] 21672 28587 30709 20873 19877
# [4,] 21672 28587 30709 19877 20873
# [5,] 21672 28587 20873 30709 19877
# [6,] 21672 28587 19877 30709 20873
# [7,] 21672 20873 28587 30709 19877
# [8,] 21672 19877 28587 30709 20873
# [9,] 20873 30709 28587 21672 19877
#[10,] 20873 30709 28587 19877 21672
#[11,] 20873 28587 30709 21672 19877
#[12,] 20873 28587 30709 19877 21672   ####
#[13,] 20873 28587 21672 30709 19877
#[14,] 20873 28587 19877 30709 21672
#[15,] 20873 21672 28587 30709 19877
#[16,] 20873 19877 28587 30709 21672

R order vectors so that difference between most of the elements are positive

3 Answers3