草庐IT

javascript - 根据用户的偏好对一组对象进行排序

coder 2024-05-11 原文

给定一组没有特定顺序的 n 个对象(本例中为 n = 5):

{
    apple,
    orange,
    banana,
    cherry,
    cabbage
}

我试图通过三个选项向用户提出几个问题，如下所示:

banana      vs.      cabbage
      (no preference)

在每个问题之后，它会提出一个具有不同选项的新问题(没有偏好保持不变)，有效地收集有关用户偏好的数据。

它会在几个(在本例中为 6 或 7 个)问题之后，按顺序给出排名最高的对象的有序列表(数组):

{
    cherry,
    cabbage,
    orange,
    apple,
    banana
}

但是，我不知道这样的算法将如何工作或何时知道停止。如果这是一个糟糕的问题，我很抱歉，但我对算法设计还很陌生。

我想这并不重要，但我使用的是 JavaScript。

好吧，四个月后我会重新审视这个问题，因为我想到了一种新的排序方法。

也许，为每个对象列出一个劣等对象的列表会更有效，这样任何低于一个对象的东西都会低于它的上级对象。我解释得很糟糕，所以这是一个视觉效果:

cherry > cabbage
cabbage > banana
cabbage > apple
apple > orange

thus, cherry > cabbage & banana & apple & orange

用老方法，分数:

apple vs. orange
apple vs. banana (e.g. apple wins)
apple vs. cherry (e.g. cherry wins)
apple vs. cabbage
orange vs. banana
orange vs. cherry
orange vs. cabbage
banana vs. cherry
banana vs. cabbage
cherry vs. cabbage

10 questions

新方法会使 cherry vs. banana 变得多余，因为我们已经知道 apple > banana 和 cherry > apple。我真的只需要弄清楚如何编码。

唯一的问题出现在人类循环逻辑(即 a > b > c > a)中，这是可能的，但幸运的是，这不会成为我的特定集合的问题。

最佳答案

我前段时间在回答相关问题 (Collaborative sorting algorithm based on 1 vs 1 choice) 时对此进行了调查，发现创建一个基于“你喜欢 A 还是 B？”的有序列表样式问题，使用尽可能少的问题，同时避免循环(如:A>B，B>C，C>A)，最好使用二进制插入排序或其变体来完成。

这在实践中意味着，您将元素一个一个地引入有序列表，找到它们在列表中的位置，插入它们，然后移动到下一个元素。
为了将比较次数减少到最严格的最小值，可以使用二进制插入；这意味着每个新元素首先与有序列表中间的元素进行比较；这告诉你新元素是在上半部分还是下半部分；然后将它与那一半中间的元素进行比较，依此类推，直到找到它的位置。

例如，考虑一个包含 10 个需要排序的元素的列表。如果将每个元素与其他所有元素进行比较，则需要问 45 个问题。通过二进制插入，这减少到 19 ~ 25 个问题，平均 22.2 个问题。

问题的确切数量取决于输入:要将 1 插入列表 [2,4,6,8]，您需要将它与 4 进行比较，然后是2，比较两次就知道它的位置了；要将 7 插入列表 [2,4,6,8]，您需要将它与 4 进行比较，然后再与 进行比较6，然后跟8，比较3次才知道它的位置。通常，插入第 n 个元素需要进行 log2(n) 或 log2(n)+1 次比较(总是 log2 (n) 如果 n 是 2 的幂)。总的比较次数<>e(n)。

如果您接受“无偏好”的答案，问题的数量可以减少，如果大多数答案都是“无偏好”，则问题数量可以减少到 n-1。

下面是我为相关问题编写的 Javascript 代码片段。它问“A还是B？”问题，将“A”、“B”或“无偏好”作为答案，并创建一个有序列表。随机生成器充当给出答案的人。

该算法可以适用于就地对数组进行排序。您首先将第一个元素视为排序数组，将第二个元素视为要插入的元素，并在必要时交换它们；那么您会将前两个元素视为排序列表，将第三个元素视为要插入的元素，依此类推。有关二进制插入排序的变体以及减少交换次数的策略，请参见例如this Wikipedia article .

function PrefList(n) {
    this.size = n;
    this.items = [{item: 0, equals: []}];
    this.current = {item: 1, try: 0, min: 0, max: 1};

    this.addAnswer = function(x, y, pref) {
        if (pref == 0) {
            this.items[this.current.try].equals.push(this.current.item);
            this.current = {item: ++this.current.item, try: 0, min: 0, max: this.items.length};
        } else {
            if (pref == -1) this.current.max = this.current.try
            else this.current.min = this.current.try + 1;
            if (this.current.min == this.current.max) {
                this.items.splice(this.current.min, 0, {item: this.current.item, equals: []});
                this.current = {item: ++this.current.item, try: 0, min: 0, max: this.items.length};
            }
        }
    }

    this.getQuestion = function() {
        if (this.current.item >= this.size) return null;
        this.current.try = Math.floor((this.current.min + this.current.max) / 2);
        return({a: this.current.item, b: this.items[this.current.try].item});
    }

    this.getOrder = function() {
        var index = [];
        for (var i in this.items) {
            var equal = [this.items[i].item];
            for (var j in this.items[i].equals) {
                equal.push(this.items[i].equals[j]);
            }
            index.push(equal);
        }
        return(index);
    }
}

// THIS FUNCTION ACTS AS THE PERSON ANSWERING THE QUESTIONS
function preference(a, b) {
    if (Math.random() > 0.6) return -1; else if (Math.random() > 0.333) return  1; else return 0;
}

// CREATE TABLE AND ASK QUESTIONS UNTIL TABLE IS COMPLETE
var fruit = ["orange", "apple", "pear", "banana", "kiwifruit", "grapefruit", "peach", "cherry", "starfruit", "strawberry"];
var t = new PrefList(10), c = 0, q;
while (q = t.getQuestion()) {
    document.write(++c + ". " + fruit[q.a] + " or " + fruit[q.b] + "?<BR>");
    var answer = preference(fruit[q.a], fruit[q.b]);
    document.write("&nbsp;&rarr; " + [fruit[q.a], "no preference", fruit[q.b]][answer + 1] + "<BR>");
    t.addAnswer(q.a, q.b, answer);
}

// PERFORM SORT BASED ON TABLE AND DISPLAY RESULT
var index = t.getOrder();
document.write("LIST IN ORDER:<BR>");
for (var i = 0, pos = 1; i < index.length; i++) {
    var pre = pos + ". ";
    for (var j = 0; j < index[i].length; j++) {
        document.write(pre + fruit[index[i][j]] + "<BR>");
        pre = "&nbsp;&nbsp;&nbsp;&nbsp;";
    }
    pos += index[i].length;
}

关于javascript - 根据用户的偏好对一组对象进行排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31298996/

偏好javascriptcodethiscurrentalgorithmsorting

有关javascript - 根据用户的偏好对一组对象进行排序的更多相关文章

  1. ruby - 如何从 ruby​​ 中的字符串运行任意对象方法？ - 2

    总的来说，我对ruby​​还比较陌生，我正在为我正在创建的对象编写一些rspec测试用例。许多测试用例都非常基础，我只是想确保正确填充和返回值。我想知道是否有办法使用循环结构来执行此操作。不必为我要测试的每个方法都设置一个assertEquals。例如:describeitem,"TestingtheItem"doit"willhaveanullvaluetostart"doitem=Item.new#HereIcoulddotheitem.name.shouldbe_nil#thenIcoulddoitem.category.shouldbe_nilendend但我想要一些方法来使用

  2. ruby-on-rails - 使用 Ruby on Rails 进行自动化测试 - 最佳实践 - 2

    很好奇，就使用ruby​​onrails自动化单元测试而言，你们正在做什么？您是否创建了一个脚本来在cron中运行rake作业并将结果邮寄给您？git中的预提交Hook？只是手动调用？我完全理解测试，但想知道在错误发生之前捕获错误的最佳实践是什么。让我们理所当然地认为测试本身是完美无缺的，并且可以正常工作。下一步是什么以确保他们在正确的时间将可能有害的结果传达给您？ 最佳答案 不确定您到底想听什么，但是有几个级别的自动代码库控制:在处理某项功能时，您可以使用类似autotest的内容获得关于哪些有效，哪些无效的即时反馈。要确保您的提

  3. ruby-on-rails - 按天对 Mongoid 对象进行分组 - 2

    在控制台中反复尝试之后，我想到了这种方法，可以按发生日期对类似activerecord的(Mongoid)对象进行分组。我不确定这是完成此任务的最佳方法，但它确实有效。有没有人有更好的建议，或者这是一个很好的方法？#eventsisanarrayofactiverecord-likeobjectsthatincludeatimeattributeevents.map{|event|#converteventsarrayintoanarrayofhasheswiththedayofthemonthandtheevent{:number=>event.time.day,:event=>ev

  4. ruby - 使用 C 扩展开发 ruby​​gem 时，如何使用 Rspec 在本地进行测试？ - 2

    我正在编写一个包含C扩展的gem。通常当我写一个gem时，我会遵循TDD的过程，我会写一个失败的规范，然后处理代码直到它通过，等等......在“ext/mygem/mygem.c”中我的C扩展和在gemspec的“扩展”中配置的有效extconf.rb，如何运行我的规范并仍然加载我的C扩展？当我更改C代码时，我需要采取哪些步骤来重新编译代码？这可能是个愚蠢的问题，但是从我的gem的开发源代码树中输入“bundleinstall”不会构建任何native扩展。当我手动运行rubyext/mygem/extconf.rb时，我确实得到了一个Makefile(在整个项目的根目录中)，然后当

  5. ruby-on-rails - 如何验证非模型(甚至非对象)字段 - 2

    我有一个表单，其中有很多字段取自数组(而不是模型或对象)。我如何验证这些字段的存在？solve_problem_pathdo|f|%>... 最佳答案 创建一个简单的类来包装请求参数并使用ActiveModel::Validations。#definedsomewhere,atthesimplest:require'ostruct'classSolvetrue#youcouldevencheckthesolutionwithavalidatorvalidatedoerrors.add(:base,"WRONG!!!")unlesss

  6. Ruby 写入和读取对象到文件 - 2

    好的，所以我的目标是轻松地将一些数据保存到磁盘以备后用。您如何简单地写入然后读取一个对象？所以如果我有一个简单的类classCattr_accessor:a,:bdefinitialize(a,b)@a,@b=a,bendend所以如果我从中非常快地制作一个objobj=C.new("foo","bar")#justgaveitsomerandomvalues然后我可以把它变成一个kindaidstring=obj.to_s#whichreturns""我终于可以将此字符串打印到文件或其他内容中。我的问题是，我该如何再次将这个id变回一个对象？我知道我可以自己挑选信息并制作一个接受该信

  7. ruby-on-rails - 如果 Object::try 被发送到一个 nil 对象，为什么它会起作用？ - 2

    如果您尝试在Ruby中的nil对象上调用方法，则会出现NoMethodError异常并显示消息:"undefinedmethod‘...’fornil:NilClass"然而，有一个tryRails中的方法，如果它被发送到一个nil对象，它只返回nil:require'rubygems'require'active_support/all'nil.try(:nonexisting_method)#noNoMethodErrorexceptionanymore那么try如何在内部工作以防止该异常？ 最佳答案 像Ruby中的所有其他对象

  8. ruby-on-rails - 使用 rails 4 设计而不更新用户 - 2

    我将应用程序升级到Rails4，一切正常。我可以登录并转到我的编辑页面。也更新了观点。使用标准View时，用户会更新。但是当我添加例如字段:name时，它​​不会在表单中更新。使用devise3.1.1和gem'protected_attributes'我需要在设备或数据库上运行某种更新命令吗？我也搜索过这个地方，找到了许多不同的解决方案，但没有一个会更新我的用户字段。我没有添加任何自定义字段。 最佳答案 如果您想允许额外的参数，您可以在ApplicationController中使用beforefilter，因为Rails4将参数

  9. ruby-on-rails - 未在 Ruby 中初始化的对象 - 2

    我在Rails工作并有以下类(class):classPlayer当我运行时bundleexecrailsconsole然后尝试:a=Player.new("me",5.0,"UCLA")我回来了:=>#我不知道为什么Player对象不会在这里初始化。关于可能导致此问题的操作/解释的任何建议？谢谢，马里奥格 最佳答案 havenoideawhythePlayerobjectwouldn'tbeinitializedhere它没有初始化很简单，因为你还没有初始化它!您已经覆盖了ActiveRecord::Base初始化方法，但您没有调

  10. ruby - 如何进行排列以有效地定制输出 - 2

    这是一道面试题，我没有答对，但还是很好奇怎么解。你有N个人的大家庭，分别是1,2,3,...,N岁。你想给你的大家庭拍张照片。所有的家庭成员都排成一排。“我是家里的friend，建议家庭成员安排如下:”1岁的家庭成员坐在这一排的最左边。每两个坐在一起的家庭成员的年龄相差不得超过2岁。输入:整数N，1≤N≤55。输出:摄影师可以拍摄的照片数量。示例->输入:4，输出:4符合条件的数组:[1,2,3,4][1,2,4,3][1,3,2,4][1,3,4,2]另一个例子:输入:5输出:6符合条件的数组:[1,2,3,4,5][1,2,3,5,4][1,2,4,3,5][1,2,4,5,3][

随机推荐