списка воспроизведения в случайном порядке, чтобы максимально увеличить расстояние между аналогичными элементами

Question

В списке адресов

http://a.com/foo http://b.com/bar http://a.com/monkey http://c.com/prune http://a.com/bear http://b.com/walrus http://b.com/baz http://b.com/plugh

Я хочу, чтобы максимизировать расстояние между любой парой a.com-х, любой парой b.com 's и т.д. Это должно быть дешевым, но не обязательно быть оптимальным. (Я использую список URL-адресов для загрузки файлов с веб-сайтов a.com, b.com, c.com и не желаю посещать какой-либо конкретный сайт с более высокой частотой, чем необходимо. В этом примере мы удалили сайт b.com 3 раза подряд , чего следует избегать.)

Мне идеально понравилась бы библиотека Java, но я бы согласился на псевдокод. Maximise sum of pairwise distances in array похоже на аналогичную проблему, но у меня нет простого ответа - я просто хочу что-то, что «достаточно хорошо»

Answer 1

Поскольку ответов нет, я написал свои собственные. Это очень грубо, но работает. Он считывает список URL-адресов, извлекает хосты, подсчитывает их, а затем заполняет массив с голубями с индексами, пропорциональными обратной частоте хостов.

package org.xmlcml.cmine.util; 

import java.util.ArrayList; 
import java.util.HashMap; 
import java.util.List; 
import java.util.Map; 

import org.apache.log4j.Level; 
import org.apache.log4j.Logger; 

import com.google.common.collect.HashMultiset; 
import com.google.common.collect.Multiset; 

public class URLShuffler { 

    public static final Logger LOG = Logger.getLogger(URLShuffler.class); 
    static { 
     LOG.setLevel(Level.DEBUG); 
    } 

// в случае необходимости дополнительных ящичков, но это, кажется, не для средних проблем

private static int TOL = 1; 
    private List<String> urls; 
    private Multiset<String> domains; 
    private Map<String, Integer> currentIndexByDomain; 
    private Map<String, Integer> countByDomain; 
    private List<String> outputUrls; 

    public URLShuffler() { 

    } 

    public void readURLs(List<String> urls) { 
     this.urls= urls; 
     domains = HashMultiset.create(); 
     for (String url : urls) { 
      String domain = getDomain(url); 
      domains.add(domain); 
     } 
     LOG.debug(domains); 
    } 

// this would be better using java.net.URL 

    private String getDomain(String url) { 
     int idx = url.indexOf("//"); 
     if (idx != -1) { 
      url = url.substring(idx+2); 
     } 
     idx = url.indexOf("/"); 
     String domain = url.substring(0, idx); 
     return domain; 
    } 

    public List<String> getShuffledUrls() { 
     currentIndexByDomain = new HashMap<String, Integer>(); 
     countByDomain = new HashMap<String, Integer>(); 

     outputUrls = new ArrayList<String>(); 
     for (int i = 0; i < urls.size() * TOL; i++) { 
      outputUrls.add(""); 
     } 

// это удобный метод упаковки Guava вид.

 for (Multiset.Entry<String> entry : CMineUtil.getEntriesSortedByCount(domains)) { 
      LOG.debug(entry); 
      countByDomain.put(entry.getElement(), entry.getCount()); 
      currentIndexByDomain.put(entry.getElement(), entry.getCount() - 1); 
     } 
     for (String url : urls) { 
      String domain = getDomain(url); 
      Integer currentIndex = currentIndexByDomain.get(domain); 
      Integer count = countByDomain.get(domain); 
      int slot = (urls.size() * currentIndex * TOL)/count; 
      currentIndexByDomain.put(domain, currentIndex - 1); 
      addUrl(url, slot); 
     } 
     return outputUrls; 
    } 

    private void addUrl(String url, int slot) { 
     boolean filled = fillLower(url, slot); 
     if (!filled) { 
      fillUpper(url, slot); 
     } 
    } 

// if slot is not free run upwards till next free slot 

    private boolean fillUpper(String url, int slot) { 
     for (int i = slot; i < outputUrls.size(); i++) { 
      if (fill(url, i)) { 
       return true; 
      } 
     } 
     return false; 
    } 

// if slot is not free run downwards till next free slot 
    private boolean fillLower(String url, int slot) { 
     for (int i = slot; i >= 0; i--) { 
      if (fill(url, i)) { 
       return true; 
      } 
     } 
     return false; 
    } 

    private boolean fill(String url, int slot) { 
     if (outputUrls.get(slot).equals("")) { 
      outputUrls.set(slot, url); 
      return true; 
     } 
     return false; 
    } 
} 

`` `